题目描述

游戏中共有 $N$ 种怪兽。消灭一头第 $i$ 种怪兽需要消耗 $A_i$ 点魔力，每轮游戏都会出现 $C_i$ 头这种怪兽。

每轮游戏开始时，小 A 获得一定的魔力。他会先按照消灭一头怪兽所需的魔力从大到小排列怪兽种类，再按此顺序逐种处理。处理一种怪兽时，他会在剩余魔力允许的情况下尽可能多地消灭这种怪兽，然后继续处理下一种怪兽，直到所有种类都处理完毕。

现在进行 $M$ 轮相互独立的游戏。第 $j$ 轮开始时，小 A 拥有 $V_j$ 点魔力。请计算每轮能够消灭的怪兽数量。

输入格式

第一行包含两个整数 $N,M$，分别表示怪兽种类数和游戏轮数。

接下来 $N$ 行，每行包含两个整数 $A_i,C_i$，分别表示消灭一头第 $i$ 种怪兽所需的魔力和这种怪兽的数量。

接下来 $M$ 行，每行包含一个整数 $V_j$，表示第 $j$ 轮开始时拥有的魔力。

输出格式

输出 $M$ 行，第 $j$ 行输出一个整数，表示第 $j$ 轮能够消灭的怪兽数量。

3 3
5 1
20 2
30 3
45
200
2

2
6
0

样例解释

第一轮先消灭一头需要 $30$ 点魔力的怪兽，剩余 $15$ 点魔力不足以继续消灭这种怪兽；随后处理下一种怪兽，仍然无法消灭；最后消灭一头需要 $5$ 点魔力的怪兽，因此共消灭 $2$ 头。

数据范围与提示

• $1 \le N,M \le 10^5$
• $1 \le A_i \le 10^9$
• $1 \le C_i \le 10^4$
• $0 \le V_j \le 10^{18}$