Приближается лунный новый год, поэтому Боб хочет поужинать в знаменитом ресторане «У Алисы».
В ресторане «У Алисы» можно заказать \(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\)-го типа, будет выполнен следующий алгоритм.
- Если \(r_i > 0\), то посетителю подадут \(1\) блюдо \(i\)-го типа. Стоимость этого блюда будет равна \(c_i\). В то же время \(r_i\) уменьшится на \(1\).
- Иначе посетителю подадут \(1\) самое дешевое блюдо из тех, что еще остались, если, конечно, такие еще есть. Если есть несколько доступных самых дешевых типов, подадут блюдо, тип которого имеет наименьший номер. Стоимость будет равна стоимости поданного блюда, а его остаток будет уменьшен на \(1\).
- Если не осталось вообще никаких блюд, то посетитель уйдет недовольным и ничего не заплатит. Независимо от того, сколько блюд ему подали до этого, счет посетителя равен \(0\).
Если посетитель не уйдет до того, как ему подали все \(d_j\) блюд, то его общий счет будет равен суммарной стоимости всех поданных \(d_j\) блюд.
Определите счет для каждого из \(m\) посетителей.
Выходные данные
Выведите \(m\) строк. В \(j\)-й строке выведите счет \(j\)-го посетителя.
Примечание
В первом примере \(5\) посетителей будут обслужены следующим образом.
- Посетителю \(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\) подадут \(4\) блюд \(1\)-го типа. Счет равен \(4 \cdot 6 = 24\). Остатки будут равны \(\{4, 0, 2, 0, 4, 4, 7, 5\}\).
- Посетителю \(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\) подадут \(2\) блюда \(3\)-го типа, \(2\) блюда \(8\)-го типа. Остатки будут равны \(2 \cdot 3 + 2 \cdot 2 = 10\). The remain will be \(\{4, 0, 0, 0, 4, 0, 7, 0\}\).
- Посетителю \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
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
|
36
11058
99996
4333326
0
0
|