C. Запас билетов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Maître Gims - Est-ce que tu m'aimes ?
ඞ

Будучи генеральным директором стартапа, вы хотите наградить каждого из $$$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$$$ билетов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^9, 1 \le k \le \min(nm, 10^9)$$$) — количество дней продажи, максимальное количество билетов, которое можно купить в каждый день, и количество билетов, которые нужно купить.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — цена одного билета на каждый из предстоящих $$$n$$$ дней.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальную сумму денег, необходимую для покупки ровно $$$k$$$ билетов.

Пример
Входные данные
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
Примечание

В первом наборе входных данных один из оптимальных способов покупки $$$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$$$.