当前没有测试数据。

题目描述

在《魔法世界》的游戏中，小 $A$ 是一位魔法师，他的任务是消灭游戏中的怪兽，从而获得经验，提升自己的等级。

每轮游戏开始时，小 $A$ 会获得一定的魔力值，小 $A$ 在每轮游戏开始时获得的魔力值 可能是不同的。

每轮游戏地图中会产生 $N$ 种不同类型的怪兽（编号为 $1 \sim N$）。如果小 $A$ 要消灭 1 头 第 $i$ 种类型的怪兽（编号为 $i$），需要消耗 $A_i$ 个单位的魔力值。在每轮游戏中，第 $i$ 种类型的怪兽会固定的出现 $C_i$ 头。

消灭怪兽需要的魔力值越高，玩家能得到的经验值就越高，越容易提升自己的等级。作为资深玩家的小 $A$，迫切期待提升自己的等级。因此，每轮游戏，他都会 将所有怪兽按照魔力值降序排序，然后在魔力值允许的情况下，按顺序依次 尽可能消灭怪兽。直到地图中没有怪兽，或者自己的魔力值不足以继续消灭怪兽。

请编程计算出，如果游戏进行 $M$ 轮，第 $i$ 轮游戏开始小 $A$ 获得了 $V_i$ 个单位的魔力值，在每轮游戏中，他可以消灭多少个怪兽。

输入格式

第 $1$ 行读入 $2$ 个整数 $N$ 和 $M$，代表每轮游戏中出现的怪兽种类数和游戏轮数。

接下来 $N$ 行，每行读入 $2$ 个整数 $A_i$ 和 $C_i$，分别代表消灭 $1$ 头第 $i$ 种怪兽，需要消耗的魔力值，和第 $i$ 种怪兽出现的头数。

接下来 $M$ 行，每行读入一个整数 $V_i$，代表每轮游戏开始时，小 $A$ 获得的魔力值。

输出格式

输出 $M$ 行，分别代表每轮游戏结束时，小 $A$ 消灭了多少个怪兽。

样例

输入

3 3
5 1
20 2
30 3
45
200
2

输出

2
6
0

数据范围

对于 $20\%$ 的数据，满足 $1 \le N, M \le 1000$。

对于 另外 $40\%$ 的数据，满足 $C_i = 1$。

对于 $100\%$ 的数据，满足 $1 \le N, M \le 10^5$，$1 \le A_i \le 10^9$，$1 \le C_i \le 10000$，$0 \le V_i \le 10^{18}$。