题目描述

王大锤同学最近沉迷于一款名为《大船上的夜晚》的游戏。在该游戏中，玩家需要扮演知名制药公司兼雇佣兵集团Rhodes Island的领导人之一——“博士”，与反派组织Reunion展开对抗。由于该公司在训练、晋升员工的过程中需要耗费大量的金钱，因此该公司常年陷入财政危机。为了救公司于水火，“博士”决定对附近的若干个反派据点展开一次大讨伐，夺取敌人的储备资金。已知附近有\(N\)个据点可供选择，攻下第\(i\)个据点之后可以获得\(w_i\)元的资金。当然敌人的实力也不容小视，第\(i\)个据点的综合防御力为\(d_i\)，要想攻下该据点，我方的战力值必须\(\ge d_i\)。
现有\(Q\)次询问，每次询问给定一个参数\(W\)，要求输出：如果“博士”决定紧急组建一只战斗力为\(A\)的讨伐队伍，剿灭所有防御力\(\le A\)的敌人据点，获取不少于\(W\)的资金，那么\(A\)的最小值应该设为多少？

输入格式

第一行是两个正整数\(N, Q\)；
之后\(N\)行，每行两个正整数\(d_i, w_i\)，表示该据点的防御力以及被剿灭后我方可获取的资金；
之后\(Q\)行，每行一个正整数\(W\)，表示该次询问的参数。输入保证\(W \le \displaystyle\sum_{i=1}^{N} w_i\)

输出格式

输出\(Q\)行，每行一个整数表示该次询问的答案。

样例

输入

4 3
2 5
3 8
4 6
6 7
5
10
20

输出

2
3
6

数据规模及约定

30%的数据：\(N, Q \le 2000, \quad d_i \le 2000\)
60%的数据：\(N, Q \le 2000\)
100%的数据：\(N, Q \le 2 \times 10^5, \quad 1 \le d_i, w_i \le 10^9\)
时间限制1s，空间限制64MB。