1590 . 蚯蚓之搭公車問題 Bus
TopCoder
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 1
2 1
9 5
10 5
15
9 5
10 5
15
Sample Output 1
10
Hints
蚯蚓其實沒有常常遲到。
Problem Source
原TIOJ1590 / Problem Setter: coquelicot
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |