B. Лунный новый год и заказ еды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Приближается лунный новый год, поэтому Боб хочет поужинать в знаменитом ресторане «У Алисы».

В ресторане «У Алисы» можно заказать $$$n$$$ типов блюд. Цена одного блюда $$$i$$$-го типа всегда равна $$$c_i$$$. Изначально в ресторане достаточно ингредиентов для подачи ровно $$$a_i$$$ блюд $$$i$$$-го типа. В канун лунного нового года $$$m$$$ посетителей зайдут в ресторан один за другим, при этом $$$j$$$-й клиент закажет $$$d_j$$$ блюд $$$t_j$$$-го типа. $$$(i + 1)$$$-й посетитель придет лишь после того, как $$$i$$$-й посетитель будет полностью обслужен.

Предположим, в некоторый момент времени осталось ровно $$$r_i$$$ блюд $$$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$$$-го посетителя.

Примеры
Входные данные
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
Выходные данные
22
24
14
10
39
Входные данные
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
Выходные данные
36
396
3996
39996
399996
0
Входные данные
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
Выходные данные
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$$$. The remain will be $$$\{4, 0, 2, 0, 4, 0, 7, 2\}$$$.
  4. Посетителю $$$4$$$ подадут $$$2$$$ блюда $$$3$$$-го типа, $$$2$$$ блюда $$$8$$$-го типа. Остатки будут равны $$$2 \cdot 3 + 2 \cdot 2 = 10$$$. The remain will be $$$\{4, 0, 0, 0, 4, 0, 7, 0\}$$$.
  5. Посетителю $$$5$$$ подадут $$$7$$$ блюд $$$7$$$-го типа, $$$3$$$ блюда $$$1$$$-го типа. Остатки будут равны $$$7 \cdot 3 + 3 \cdot 6 = 39$$$. The remain will be $$$\{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$$$.