F. Задача про нейронную сеть
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы хотите натренировать модель нейронной сети для вашей выпускной работы. В датасете находятся $$$n$$$ изображений, размер $$$i$$$-го изображения равен $$$a_i$$$ байт.

В вашем распоряжении нет мощных удаленных серверов для того, чтобы натренировать модель, поэтому вам необходимо сделать это на вашем собственном компьютере. Но есть небольшая проблема: общий размер датасета слишком большой для вашего компьютера, поэтому вы решили удалить некоторые изображения... С другой стороны, вы не хотите делать датасет слишком некачественным, поэтому вы можете удалить из него не более чем $$$k$$$ изображений. Заметьте, что вы можете только удалять изображения, вы не можете менять их порядок.

Вы хотите удалить эти изображения оптимальным образом, поэтому вы придумали метрику (вы же все-таки data scientist), которая позволяет оценить результат удалений. Рассмотрим массив $$$b_1, b_2, \ldots, b_m$$$ после удаления не более $$$k$$$ изображений ($$$n - k \le m \le n$$$). Данные из этого массива будут загружены в компьютер блоками по $$$x$$$ последовательных элементов каждый. Более точно:

  • элементы с индексами от $$$1$$$ до $$$x$$$ ($$$b_1, b_2, \ldots, b_x$$$) принадлежат первому блоку;
  • элементы с индексами от $$$x + 1$$$ до $$$2x$$$ ($$$b_{x + 1}, b_{x + 2}, \ldots, b_{2x}$$$) принадлежат второму блоку;
  • элементы с индексами от $$$2x + 1$$$ до $$$3x$$$ ($$$b_{2x + 1}, b_{2x + 2}, \ldots, b_{3x}$$$) принадлежат третьему блоку;
  • и так далее.

Всего блоков будет $$$cnt = \left\lceil\frac{m}{x}\right\rceil$$$. Заметьте, что если $$$m$$$ не делится на $$$x$$$, то последний блок содержит меньше $$$x$$$ элементов, и это нормально.

Пусть $$$w(i)$$$ равно общему размеру $$$i$$$-го блока, то есть сумме размеров изображений внутри этого блока. Например, размер первого блока $$$w(1)$$$ равен $$$b_1 + b_2 + \ldots + b_x$$$, размер второго блока $$$w(2)$$$ равен $$$b_{x + 1} + b_{x + 2} + \ldots + b_{2x}$$$.

Значением метрики, которую вы придумали, является максимальный размер блока по всем блокам результирующего датасета. Другими словами, значение метрики равно $$$\max\limits_{i=1}^{cnt} w(i)$$$.

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

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

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

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$), где $$$a_i$$$ равно размеру $$$i$$$-го изображения.

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

Выведите одно число: минимальное значение метрики, описанной в условии задачи, которое возможно получить после удаления не более $$$k$$$ изображений из датасета.

Примеры
Входные данные
5 5 4
1 1 5 4 5
Выходные данные
0
Входные данные
5 2 4
6 1 5 5 6
Выходные данные
11
Входные данные
6 1 4
3 3 1 3 1 2
Выходные данные
8
Входные данные
6 1 3
2 2 1 2 2 1
Выходные данные
5
Примечание

В первом тестовом примере вы можете удалить весь массив, поэтому ответ равен $$$0$$$.

Во втором тестовом примере вы можете удалить первый и последний элементы $$$a$$$ и получить $$$b = [1, 5, 5]$$$. Размер первого (и единственного) блока равен $$$11$$$. Таким образом, ответ равен $$$11$$$.

В третьем тестовом примере вы можете удалить второй элемент $$$a$$$ и получить $$$b = [3, 1, 3, 1, 2]$$$. Размер первого блока равен $$$8$$$, а размер второго блока равен $$$2$$$. Таким образом, ответ равен $$$8$$$.

В четвертом тестовом примере вы можете оставить массив $$$a$$$ без изменений и получить $$$b = [2, 2, 1, 2, 2, 1]$$$. Размер первого блока равен $$$5$$$, как и размер второго. Таким образом, ответ равен $$$5$$$.