第八届“英拿科技杯”上海高校金马程序设计联赛暨东华大学邀请赛

I. 孤星

单点时限: 2.0 sec

内存限制: 512 MB

n(1103) 个干员,每个干员工资为 wi(1wi105),贡献值为 vi(1vi102)

给出 m(1m105)次询问,每次询问:当你能承受的总工资为 W(0W109) 时,能收获最大的贡献值是多少。

输入格式

第一行,两个整数 n,m

接下来 n 行,每行两个整数 wi,vi,表示每个干员的工资和贡献值。

接下来m行,每行一个数 W,表示单次询问中的可以承受的总工资。

输出格式

输出共m行,每行一个数表示你的答案。

样例

Input
4 3
1 2
2 1
1 1
2 3
5
1
0
Output
6
2
0