User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

45.7% (21/46)

Tags

Description

曾經有位常常遲到的學生叫作蚯蚓,

在拿過不計其數張的黃單,做過不計其數次的愛校以後,

他有天再也無法忍受愛校了!發憤的蚯蚓決定以後不要再遲到!

然而江山易改,本性難移,蚯蚓依然希望能越晚出門越好,

他已經成功的查到所有公車資訊,可是資料竟多到他無法處理!

於是蚯蚓找上了你,希望聰明的你能幫助他計算出答案。

為人善良正直又熱心助人的你,是否能達成蚯蚓的期盼呢?

Input Format

第一行有兩個數字 n m ,代表有 n 輛公車 m 個詢問。

接下來 n 行,每行兩個數字 s c ,代表公車的發車時間 與 行車時間。

之後的 m 行,每行一個數字 q ,代表蚯蚓想在時間 q 以前到達目的地。

n ≦ 500000, m ≦ 500000

s ≦ 107, c ≦ 107, q ≦ 2*107

Output Format

對於每個詢問請輸出蚯蚓最晚何時要搭上車。

如果無論如何都搭不上車,請輸出 -1 。

Sample Input

2 1
9 5
10 5
15

Sample Output

10

Hints

蚯蚓其實沒有常常遲到。

Problem Source

原TIOJ1590 / Problem Setter: coquelicot

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 8000 65536 262144
1 8000 65536 262144
2 8000 65536 262144
3 8000 65536 262144
4 8000 65536 262144