题目描述

王大锤同学最近沉迷于一款名为《大船上的夜晚》的游戏。在该游戏中，玩家需要扮演知名制药公司兼雇佣兵集团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。