Lunar New Year and Food Ordering

Description:

Input:

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.

Output:

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

Sample Input:

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

Sample Output:

22
24
14
10
39

Sample Input:

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

Sample Output:

36
396
3996
39996
399996
0

Sample Input:

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

Sample Output:

36
11058
99996
4333326
0
0

Note:

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$$$.