410765: GYM104099 3 Горилла Коко возвращается

3. Горилла Коко возвращаетсяограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Зачем горилла Коко прыгала по лианам? Оказывается, что у нее была вполне конкретная цель: Коко спешила на обед.

Обед гориллы организован следующим образом. В начале ей выдают поднос, на котором разложены $$$n$$$ фруктов, пронумерованных числами от $$$1$$$ до $$$n$$$. Если горилла съест $$$i$$$-й фрукт, она получит $$$a_i$$$ единиц удовольствия от еды. Коко может сама выбирать, какие фрукты съесть, а какие проигнорировать. После того, как горилла съела все фрукты, которые захотела, поднос уносят, а вместо него приносят точно такой же поднос, на котором снова разложены $$$n$$$ фруктов. Затем Коко снова съедает те фрукты, которые захочет, после чего поднос уносят, и процесс продолжается аналогично.

Однако, все не так просто: горилла Коко очень любит разнообразие. Поэтому если в какой-то момент она съест $$$i$$$-й фрукт, принесенный ей на подносе, то в следующий раз, когда горилла захочет снова съесть $$$i$$$-й фрукт, он принесет ей на $$$b_i$$$ единиц удовольствия меньше, чем в предыдущий раз. Иными словами, когда горилла впервые съедает $$$i$$$-й фрукт, она получает $$$a_i$$$ единиц удовольствия. Когда Коко съедает $$$i$$$-й фрукт во второй раз, она получает $$$a_i - b_i$$$ единиц удовольствия. Когда она захочет съесть $$$i$$$-й фрукт в третий раз, то количество единиц полученного удовольствия будет равняться $$$a_i - 2 \cdot b_i$$$, и так далее. Обратите внимание, что некоторые съеденные фрукты могут приносить горилле отрицательное количество единиц удовольствия, однако есть такие фрукты тоже можно.

Горилла Коко знает, что за сегодняшний день поднос с едой будет принесен ровно $$$k$$$ раз. Также она решила, что хочет съесть ровно $$$t$$$ фруктов за весь день (имеется ввиду именно суммарное количество фруктов с учетом того, что некоторые фрукты Коко может съесть несколько раз). Разумеется, Коко хочет, чтобы суммарное количество единиц удовольствия, полученных ей от всех съеденных фруктов, было как можно больше.

Коко является очень умной гориллой, однако математика дается ей тяжело. Помогите горилле вычислить максимально возможное суммарное количество единиц удовольствия, которые она сможет получить.

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

Первая строка содержит три целых числа $$$n$$$, $$$k$$$ и $$$t$$$ ($$$1 \le n, k \le 200\,000$$$, $$$1 \le t \le \min(200\,000, n \cdot k)$$$) — количество фруктов на подносе, количество раз, когда поднос будет принесен горилле, а также количество фруктов, которое хочет съесть горилла Коко за весь день, соответственно.

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

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — величины, на которые уменьшается количество единиц удовольствия при каждом следующем употреблении в пищу $$$i$$$-го фрукта.

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

Выведите одно целое число — максимальное суммарное количество единиц удовольствия, которое может получить горилла Коко, съев ровно $$$t$$$ фруктов за день.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача	Баллы	Ограничения	Необходимые подзадачи	Информация о проверке
0	0	Тесты из условия	—	полная
1	17	$$$n \cdot k \le 20$$$	—	первая ошибка
2	14	$$$b_i = 0$$$ для всех $$$i$$$	—	первая ошибка
3	15	Все $$$b_i$$$ попарно равны	2	первая ошибка
4	12	$$$k=t$$$	—	первая ошибка
5	18	$$$n \le 1\,000$$$, $$$k \le 1\,000$$$, $$$t \le 1\,000$$$	1	первая ошибка
6	24	Нет дополнительных ограничений	1 — 5	первая ошибка

ПримерыВходные данные

4 3 12
5 10 -2 6
0 3 1 1

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

42

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

3 10 1
-3 -5 -2
1 2 3

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

-2

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

4 3 3
10 2 3 2
6 1 2 0

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

17

Примечание

Рассмотрим первый пример. На подносе находятся четыре фрукта, поднос принесут три раза за день. Так как горилла Коко хочет съесть $$$12$$$ фруктов за день, то ей придется каждый раз есть все фрукты, которые ей принесут. В первый раз, съев все четыре фрукта, она получит $$$5 + 10 + (-2) + 6 = 19$$$ единиц удовольствия. Во второй раз, съев все фрукты, она получит $$$(5 - 0) + (10 - 3) + (-2 - 1) + (6 - 1) = 14$$$ единиц удовольствия. В третий раз горилла получит $$$(5 - 0) + (10 - 6) + (-2 - 2) + (6 - 2) = 9$$$ единиц удовольствия. Суммарно за весь день Коко получит $$$19 + 14 + 9 = 42$$$ единицы удовольствия.

Во втором примере легко показать, что оптимальное поведение Коко — съесть фрукт с номером $$$3$$$ и получить $$$-2$$$ единицы удовольствия.