Монокарп играет в компьютерную игру. Чтобы повысить уровень персонажа, он может выполнять квесты. В игре есть \(n\) квестов, пронумерованных от \(1\) до \(n\).
Монокарп может выполнять квесты согласно следующим правилам:
- \(1\)-й квест всегда доступен для выполнения;
- \(i\)-й квест доступен для выполнения, если каждый квест \(j < i\) был выполнен хотя бы раз.
Обратите внимание, что Монокарп может выполнять один и тот же квест несколько раз.
За каждое выполнение персонаж получает некоторое количество опыта:
- за первое выполнение \(i\)-го квеста он получает \(a_i\) очков опыта;
- за каждое последующее выполнение \(i\)-го квеста он получает \(b_i\) очков опыта.
Монокарп очень занятой человек, поэтому у него есть свободное время, чтобы выполнить не более \(k\) квестов. Ваша задача — посчитайте максимально возможный суммарный опыт, который Монокарп может получить, если он может выполнить не более \(k\) квестов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможный суммарный опыт, который Монокарп может получить, если он может выполнить не более \(k\) квестов.
Примечание
В первом примере одна из возможных последовательностей выполнения квестов следующая: \(1, 1, 2, 3, 2, 4, 4\); суммарный опыт равен \(\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13\) (подчеркнутые числа соответствуют первому выполнению квеста).
Во втором примере одна из возможных последовательностей выполнения квестов следующая: \(1, 1\); суммарный опыт равен \(\underline{1} + 3 = 4\).
В третьем примере одна из возможных последовательностей выполнения квестов следующая: \(1, 2, 2, 2, 3\); суммарный опыт равен \(\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1
|
13
4
15
15
|