Neural Network Problem
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 2100
Tags: *special, binary search, greedy

You want to train a neural network model for your graduation work. There are $$$n$$$ images in the dataset, the $$$i$$$-th image's size is $$$a_i$$$ bytes.

You don't have any powerful remote servers to train this model so you have to do it on your local machine. But there is a problem: the total size of the dataset is too big for your machine, so you decided to remove some images — though you don't want to make the dataset too weak so you can remove no more than $$$k$$$ images from it. Note that you can only remove images, you can't change their order.

You want to remove these images optimally so you came up with a metric (you're a data scientist after all) that allows to measure the result of removals. Consider the array $$$b_1, b_2, \ldots, b_m$$$ after removing at most $$$k$$$ images ($$$n - k \le m \le n$$$). The data from this array will be uploaded to the machine in blocks of $$$x$$$ consecutive elements each. More precisely:

- elements with indices from $$$1$$$ to $$$x$$$ ($$$b_1, b_2, \ldots, b_x$$$) belong to the first block;
- elements with indices from $$$x + 1$$$ to $$$2x$$$ ($$$b_{x + 1}, b_{x + 2}, \ldots, b_{2x}$$$) belong to the second block;
- elements with indices from $$$2x + 1$$$ to $$$3x$$$ ($$$b_{2x + 1}, b_{2x + 2}, \ldots, b_{3x}$$$) belong to the third block;
- and so on.

There will be $$$cnt = \left\lceil\frac{m}{x}\right\rceil$$$ blocks in total. Note that if $$$m$$$ is not divisible by $$$x$$$ then the last block contains less than $$$x$$$ elements, and it's okay.

Let $$$w(i)$$$ be the total size of the $$$i$$$-th block — that is, the sum of sizes of images inside this block. For example, the size of the first block $$$w(1)$$$ is $$$b_1 + b_2 + \ldots + b_x$$$, the size of the second block $$$w(2)$$$ is $$$b_{x + 1} + b_{x + 2} + \ldots + b_{2x}$$$.

The value of the metric you came up with is the maximum block size over the blocks of the resulting dataset. In other words, the value of the metric is $$$\max\limits_{i=1}^{cnt} w(i)$$$.

You don't want to overload your machine too much, so you have to remove at most $$$k$$$ images in a way that minimizes the value of the metric described above.

Input format:
The first line of the input contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le k, x \le n$$$) — the number of images in the dataset, the maximum number of images you can remove and the length of each block (except maybe for the last one), respectively.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$), where $$$a_i$$$ is the size of the $$$i$$$-th image.

Output format:
Print one integer: the minimum possible value of the metric described in the problem statement after removing no more than $$$k$$$ images from the dataset.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can remove the whole array so the answer is $$$0$$$.

In the second example, you can remove the first and the last elements of $$$a$$$ and obtain $$$b = [1, 5, 5]$$$. The size of the first (and the only) block is $$$11$$$. So the answer is $$$11$$$.

In the third example, you can remove the second element of $$$a$$$ and obtain $$$b = [3, 1, 3, 1, 2]$$$. The size of the first block is $$$8$$$ and the size of the second block is $$$2$$$. So the answer is $$$8$$$.

In the fourth example, you can keep the array $$$a$$$ unchanged and obtain $$$b = [2, 2, 1, 2, 2, 1]$$$. The size of the first block is $$$5$$$ as well as the size of the second block. So the answer is $$$5$$$.

Example input:
5 5 4
1 1 5 4 5

Example output:
0

Example input:
5 2 4
6 1 5 5 6

Example output:
11

Editorial:
Binary search is pretty obvious even from the problem statement. Let's fix the maximum sum of the block $$$sum$$$. Now we have to check if we can remove at most $$$k$$$ elements to obtain some array where each block has the sum at most $$$sum$$$.
To check it, let's implement the following greedy solution: go from left to right and maintain the priority queue of $$$x$$$ minimums. Suppose we are at the position $$$i$$$ now. Add the current element $$$a_i$$$ to the priority queue and remove the biggest element from it while its size is greater than $$$x$$$ or the sum is greater than $$$sum$$$. If the size of the queue is $$$x$$$ it also means that its sum is not greater than $$$sum$$$. Let's end the current block here (just clear the queue) and start a new one from the next position. In general, we are trying to complete the block as soon as possible. It is always optimal because the earlier we end the block — the more blocks we can create (the fewer elements we have to remove). After processing all elements, let's check if the number of elements removed is not greater than $$$k$$$.
Time complexity: $$$O(n \log^2{n})$$$.