CF1106B.Lunar New Year and Food Ordering

Lunar New Year is approaching, and Bob is planning to go for a famous restaurant — "Alice's".

The restaurant "Alice's" serves $n$ kinds of food. The cost for the $i$-th kind is always $c_i$. Initially, the restaurant has enough ingredients for serving exactly $a_i$ dishes of the $i$-th kind. In the New Year's Eve, $m$ customers will visit Alice's one after another and the $j$-th customer will order $d_j$ dishes of the $t_j$-th kind of food. The $(i + 1)$-st customer will only come after the $i$-th customer is completely served.

Suppose there are $r_i$ dishes of the $i$-th kind remaining (initially $r_i = a_i$). When a customer orders $1$ dish of the $i$-th kind, the following principles will be processed.

1. If $r_i \gt 0$, the customer will be served exactly $1$ dish of the $i$-th kind. The cost for the dish is $c_i$. Meanwhile, $r_i$ will be reduced by $1$.
2. Otherwise, the customer will be served $1$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by $1$.
3. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is $0$.

If the customer doesn't leave after the $d_j$ dishes are served, the cost for the customer will be the sum of the cost for these $d_j$ dishes.

Please determine the total cost for each of the $m$ customers.

农历新年即将来临，鲍勃计划前往一家著名的餐厅——“爱丽丝餐厅”。

“爱丽丝餐厅”提供 $n$ 种食物。第 $i$ 种食物的单价恒为 $c_i$。初始时，餐厅拥有恰好足够制作 $a_i$ 份第 $i$ 种食物的食材。在除夕夜，将有 $m$ 位顾客依次光临爱丽丝餐厅，其中第 $j$ 位顾客将点 $d_j$ 份第 $t_j$ 种食物。第 $(i + 1)$ 位顾客仅在第 $i$ 位顾客被完全服务完毕后才到来。

假设当前第 $i$ 种食物还剩余 $r_i$ 份（初始时 $r_i = a_i$）。当一位顾客点 1 份第 $i$ 种食物时，将按以下规则处理：

1. 若 $r_i \gt 0$，则该顾客将被恰好供应 1 份第 $i$ 种食物，费用为 $c_i$；同时 $r_i$ 减少 1。
2. 否则，若尚有其他种类的食物仍有库存，则该顾客将被供应 1 份当前最便宜的、仍有库存的食物；若存在多个价格相同的最便宜种类，则选择其中下标最小的那种。所供应食物的费用即为该种食物的单价，且对应种类的剩余份数 $r_k$ 减少 1。
3. 若所有种类的食物均已售罄，则该顾客将愤怒离开。因此，无论此前已供应多少份食物，该顾客的总费用为 $0$。

若该顾客在成功获得全部 $d_j$ 份食物后未离开，则其费用即为这 $d_j$ 份食物费用的总和。

请计算每位顾客（共 $m$ 位）的总费用。

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), representing the number of different kinds of food and the number of customers, respectively.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^7$), where $a_i$ denotes the initial remain of the $i$-th kind of dishes.

The third line contains $n$ positive integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^6$), where $c_i$ denotes the cost of one dish of the $i$-th kind.

The following $m$ lines describe the orders of the $m$ customers respectively. The $j$-th line contains two positive integers $t_j$ and $d_j$ ($1 \leq t_j \leq n$, $1 \leq d_j \leq 10^7$), representing the kind of food and the number of dishes the $j$-th customer orders, respectively.

第一行包含两个整数 $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$ 位顾客所点食物的种类编号及其订购份数。

Print $m$ lines. In the $j$-th line print the cost for the $j$-th customer.

输出 $m$ 行。在第 $j$ 行输出第 $j$ 位顾客的花费。

In the first sample, $5$ customers will be served as follows.

1. Customer $1$ will be served $6$ dishes of the $2$-nd kind, $1$ dish of the $4$-th kind, and $1$ dish of the $6$-th kind. The cost is $6 \cdot 3 + 1 \cdot 2 + 1 \cdot 2 = 22$. The remain of the $8$ kinds of food will be ${8, 0, 2, 0, 4, 4, 7, 5}$.
2. Customer $2$ will be served $4$ dishes of the $1$-st kind. The cost is $4 \cdot 6 = 24$. The remain will be ${4, 0, 2, 0, 4, 4, 7, 5}$.
3. Customer $3$ will be served $4$ dishes of the $6$-th kind, $3$ dishes of the $8$-th kind. The cost is $4 \cdot 2 + 3 \cdot 2 = 14$. The remain will be ${4, 0, 2, 0, 4, 0, 7, 2}$.
4. Customer $4$ will be served $2$ dishes of the $3$-rd kind, $2$ dishes of the $8$-th kind. The cost is $2 \cdot 3 + 2 \cdot 2 = 10$. The remain will be ${4, 0, 0, 0, 4, 0, 7, 0}$.
5. Customer $5$ will be served $7$ dishes of the $7$-th kind, $3$ dishes of the $1$-st kind. The cost is $7 \cdot 3 + 3 \cdot 6 = 39$. The remain will be ${1, 0, 0, 0, 4, 0, 0, 0}$.

In the second sample, each customer is served what they order except the last one, who leaves angrily without paying. For example, the second customer is served $6$ dishes of the second kind, so the cost is $66 \cdot 6 = 396$.

In the third sample, some customers may not be served what they order. For example, the second customer is served $6$ dishes of the second kind, $6$ of the third and $1$ of the fourth, so the cost is $66 \cdot 6 + 666 \cdot 6 + 6666 \cdot 1 = 11058$.

在第一个样例中，将为 $5$ 位顾客提供服务，具体如下：

1. 顾客 $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. 顾客 $2$ 将获得 $4$ 份第 $1$ 种食物。费用为 $4 \cdot 6 = 24$。剩余食物数量为 ${4, 0, 2, 0, 4, 4, 7, 5}$。
3. 顾客 $3$ 将获得 $4$ 份第 $6$ 种食物和 $3$ 份第 $8$ 种食物。费用为 $4 \cdot 2 + 3 \cdot 2 = 14$。剩余食物数量为 ${4, 0, 2, 0, 4, 0, 7, 2}$。
4. 顾客 $4$ 将获得 $2$ 份第 $3$ 种食物和 $2$ 份第 $8$ 种食物。费用为 $2 \cdot 3 + 2 \cdot 2 = 10$。剩余食物数量为 ${4, 0, 0, 0, 4, 0, 7, 0}$。
5. 顾客 $5$ 将获得 $7$ 份第 $7$ 种食物和 $3$ 份第 $1$ 种食物。费用为 $7 \cdot 3 + 3 \cdot 6 = 39$。剩余食物数量为 ${1, 0, 0, 0, 4, 0, 0, 0}$。

在第二个样例中，除最后一位顾客外，其余每位顾客均按其订单提供食物；而最后一位顾客因不满而愤怒离店，未支付任何费用。例如，第二位顾客获得 $6$ 份第 $2$ 种食物，因此费用为 $66 \cdot 6 = 396$。

在第三个样例中，部分顾客可能无法完全获得其所点的食物。例如，第二位顾客获得 $6$ 份第 $2$ 种食物、$6$ 份第 $3$ 种食物和 $1$ 份第 $4$ 种食物，因此费用为 $66 \cdot 6 + 666 \cdot 6 + 6666 \cdot 1 = 11058$。