Lunar New Year and Food Ordering

题意翻译

一家餐馆里有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个用户的花费

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

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

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

说明

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