Будучи генеральным директором стартапа, вы хотите наградить каждого из \(k\) своих сотрудников билетом на предстоящий концерт. Билеты будут продаваться в течение \(n\) дней, и с помощью машины времени вы предсказали, что цена одного билета в день \(i\) будет равна \(a_i\). Однако, чтобы предотвратить скупку билетов, организаторы концерта приняли следующие меры:
- Человек может купить не более \(m\) билетов в день.
- Если человек покупает \(x\) билетов в день \(i\), то во все последующие дни (т.е. начиная с дня \(i+1\) и далее) цена за билет будет увеличена на \(x\).
Например, если \(a = [1, 3, 8, 4, 5]\), и вы покупаете \(2\) билета в день \(1\), они будут стоить \(2\) вместе, а цены, начиная с дня \(2\), станут \([5, 10, 6, 7]\). Если в день \(2\) вы купите еще \(3\) билета, они будут вместе стоить еще \(15\), а цены, начиная с дня \(3\), станут \([13, 9, 10]\).
Найдите минимальную сумму, необходимую для покупки \(k\) билетов.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальную сумму денег, необходимую для покупки ровно \(k\) билетов.
Примечание
В первом наборе входных данных один из оптимальных способов покупки \(3\) билетов выглядит следующим образом:
- Купить \(0\) билетов в первый день. Цены на билеты в остальные дни равны \([6, 4, 2]\).
- Купить \(0\) билетов во второй день. Цены на билеты в оставшиеся дни составляют \([4, 2]\).
- Купить \(1\) билет в третий день по цене \(4\). Цена за билет в оставшийся день составляет \([3]\).
- Купить \(2\) билета в четвертый день, потратив \(6\).
Во втором наборе входных данных есть только один способ купить \(8\) билетов:
- Купить \(2\) билета в первый день, потратив \(16\). Цены на билеты в остальные дни равны \([8, 6, 4]\).
- Купить \(2\) билета во второй день, потратив \(16\). Цены на билеты в оставшиеся дни составляют \([8, 6]\).
- Купить \(2\) билета в третий день, потратив \(16\). Цена за билет в оставшийся день составляет \([8]\).
- Купить \(2\) билета в четвертый день, потратив \(16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 2 3
8 6 4 2
4 2 8
8 6 4 2
5 100 1
10000 1 100 10 1000
6 3 9
5 5 5 5 5 5
|
10
64
1
72
|