题目描述：

餐馆提供 n 个菜品编号从 1 到 n ，第 i 号菜品的数量为 ai
，价格为
ci ，共有 m 个客人来预订，第 j 个客人需要预订
tj 号菜品
dj 份。

每当客人需要一份编号为 i 的菜品时，餐馆可以执行以下操作：

给他一份编号为 i 的菜品，客人支付对应菜品的价格 ci ；

如果需要的菜品没有了，那么餐馆可以给他一份最便宜的且有余量的菜品；

如果无法继续提供任何菜品，那么当前客户会生气地离开；

若一个客户得到的菜品数量达到 d j份，那么该客户的花费 cost j

将会是这 dj 份菜品的价值之和。

如果一个客户生气地离开了，那么已经提供的菜品是无法退回到可用菜品里。请你计算每个客人的花费。

输入格式：

第一行包含两个整数 n 和 m （1≤n,m≤2∗10 4
1≤n,m≤2∗104 ）

第二行包含 n n 个整数 a 1 ,a 2 ,…,a n
a1,a2,…,an （1≤a i ≤10 5
1≤ai≤105 ）

第三行包含 n n 个整数 c 1 ,c 2 ,…,c n
c1,c2,…,cn （1≤c i ≤10 7
1≤ci≤107 ）

接下来的 m m 行，每行包含两个整数 tj 和 d j
dj （1≤t j ≤n,1≤d j ≤10 5
1≤tj≤n,1≤dj≤105 ），表示第 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