农历新年快到了,鲍勃打算去一家著名的餐厅——“Alice's”。
餐厅“Alice's”提供 $$$n$$$ 种食物。第 $$$i$$$ 种的成本始终为 $$$c_i$$$。最初,餐厅有足够的食材来提供 $$$a_i$$$ 类型的 $$$i$$$ 菜肴。除夕之夜,$$$m$$$顾客会陆续光顾Alice店,第$$$j$$$顾客会点$$$d_j$$$第$$$t_j$$$种食物的菜肴。仅当第 $$$i$$$ 客户完全得到服务后,第 $$$(i + 1)$$$ 客户才会前来。
假设还剩下 $$$i$$$ 类 $$$r_i$$$ 菜肴(最初 $$$r_i = a_i$$$)。当顾客点$$$1$$$第$$$i$$$种菜肴时,将按以下原则进行处理。
1. 如果 $$$r_i > 0$$$,则将为顾客提供恰好 $$$1$$$ 种 $$$i$$$ 的菜肴。这道菜的成本是$$$c_i$$$。同时,$$$r_i$$$将减少$$$1$$$。
2. 否则,将为顾客提供 $$$1$$$ 的最便宜的可用食物(如果有)。如果有多种最便宜的食物,则提供最便宜中指数最小的一种。成本将是所提供菜肴的成本,相应菜肴的剩余费用将减少 $$$1$$$。
3. 如果根本没有菜,顾客会生气地离开。因此,无论之前上多少道菜,顾客的成本都是$$$0$$$。
如果$$$d_j$$$菜品上完后顾客没有离开,顾客的费用将是这些$$$d_j$$$菜品的费用总和。
请确定每个 $$$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
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
注意
在第一个示例中,将为 $$$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$$$ 第二种菜肴,因此成本为 $$$66 \cdot 6 = 396$$$。
在第三个示例中,某些客户可能无法获得他们订购的服务。例如,为第二位顾客提供了 $$$6$$$ 第二种菜肴,$$$6$$$ 为第三种菜肴,$$$1$$$ 为第四种菜肴,因此成本为 $$$66 \cdot 6 + 666 \cdot 6 + 6666 \cdot 1 = 11058$$$。