You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

商店里有n种物品，第i种物品的大小为ai，价值为bi，每种物品数量无限，但每人限购一个。有m个人前来购物，第j个人的背包大小为cj，他会不停选择能装得下的最大的物品买走（大小相同的情况下，优先选择价值最高的）。你需要求出每个人购买的物品的价值和。

【输入数据】

第一行两个正整数n，m。接下来n行每行两个正整数ai，bi。接下来m行每行一个正整数cj。

【输出数据】

m行，每行一个整数表示答案。

【样例输入】

5 4
10 5
9 8
7 3
3 4
1 2
20
100
28
18

【样例输出】

15
22
18
10

【数据范围】

对于20%的数据，n,m<=1000。

对于另外30%的数据，ai,bi,cj在[1,10^12]中均匀随机。

对于100%的数据，n,m<=100000，ai,bi,cj<=10^12。