题目描述

一家餐馆里有n个菜品，第$i$个菜品有对应的数量$a_i$和价格$c_i$，现在有m个客人要来点菜，第j个客人会给出买$x_j$份菜品$y_j$份的需求。 每当客人需要一份编号为$i$菜品时，你需要执行以下操作：

1. 给他一份编号为i的菜品，花费为对应菜品的价格
2. 如果需要的菜品没有了，那么我们可以给他一份最便宜的还有剩余数量的菜品
3. 如果无法继续提供任何菜品，那么当前客户会生气地离开。

如果一个客户在提供完他要求的菜品数量后仍然没有离开,那么该客户的花费$cost_j$将会是他要求的菜品价值之和。

请注意，即使一个客户生气地离开，已经提供的菜品是不可逆的（无法退回到可用菜品里）。

要求你计算每个客户的花费。

输入

第一行两个整数n,m，分别为菜品的种数和客户的数量 接下来一行，包含n个整数，为第1到n种菜品的数量。 再接下来一行，包含n个整数，为第1到第n种菜品每盘的花费。

接下来m行，每行2个整数，为 第$j$个客户所需要的菜品种类和数量。

输出

共m行，为第1到第m个用户的花费。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示不同种类的食物和顾客数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^7$），其中 $a_i$ 表示第 $i$ 种菜品的初始剩余量。

第三行包含 $n$ 个正整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^6$），其中 $c_i$ 表示第 $i$ 种菜品一道菜的成本。

接下来 $m$ 行描述了 $m$ 位顾客的订单。第 $j$ 行包含两个正整数 $t_j$ 和 $d_j$（$1 \leq t_j \leq n$，$1 \leq d_j \leq 10^7$），表示第 $j$ 位顾客订购的食物种类和数量。

输出格式

输出 $m$ 行，其中第 $j$ 行输出第 $j$ 位顾客的消费金额。

样例 #1

样例输入 #1

8 5
8 6 2 1 4 5 7 5
6 3 3 2 6 2 3 2
2 8
1 4
4 7
3 4
6 10

样例输出 #1

22
24
14
10
39

样例 #2

样例输入 #2

6 6
6 6 6 6 6 6
6 66 666 6666 66666 666666
1 6
2 6
3 6
4 6
5 6
6 66

样例输出 #2

36
396
3996
39996
399996
0

样例 #3

样例输入 #3

6 6
6 6 6 6 6 6
6 66 666 6666 66666 666666
1 6
2 13
3 6
4 11
5 6
6 6

样例输出 #3

36
11058
99996
4333326
0
0

提示

在第一个样例中，将为 $5$ 位客人提供以下服务。

顾客 $1$ 将被提供 $6$ 道 $2$ 号菜肴、$1$ 道 $4$ 号菜肴和 $1$ 道 $6$ 号菜肴。费用为 $6 \cdot 3 + 1 \cdot 2 + 1 \cdot 2 = 22$。剩余数量 $8$ 种食物的数量将为 ${8, 0, 2, 0, 4, 4, 7, 5}$。

顾客 $2$ 将被提供 $4$ 道 $1$ 号菜肴。费用为 $4 \cdot 6 = 24$。剩余数量将为 ${4, 0, 2, 0, 4, 4, 7, 5}$。

顾客 $3$ 将被提供 $4$ 道 $6$ 号菜肴和 $3$ 道 $8$ 号菜肴。费用为 $4 \cdot 2 + 3 \cdot 2 = 14$。剩余数量将为 ${4, 0, 2, 0, 4, 0, 7, 2}$。

顾客 $4$ 将被提供 $2$ 道 $3$ 号菜肴和 $2$ 道 $8$ 号菜肴。费用为 $2 \cdot 3 + 2 \cdot 2 = 10$。剩余数量将为 ${4, 0, 0, 0, 4, 0, 7, 0}$。

顾客 $5$ 将被提供 $7$ 道 $7$ 号菜肴和 $3$ 道 $1$ 号菜肴。费用为 $7 \cdot 3 + 3 \cdot 6 = 39$。剩余数量将为 ${1, 0, 0, 0, 4, 0, 0, 0}$。

在第二个样例中，每位顾客都会得到他们点的菜肴，除了最后一个愤怒离开而不付款。例如，第二位顾客将得到 $6$ 道第二种菜肴，因此费用为 $66 \cdot 6 = 396$。

在第三个样例中，有些顾客可能得不到他们点的菜肴。例如，第二位顾客将得到 $6$ 道第二种菜肴、$6$ 道第三种菜肴和 $1$ 道第四种菜肴，因此费用为 $66 \cdot 6 + 666 \cdot 6 + 6666 \cdot 1 = 11058$。