407965: GYM102953 2 Array Condensation

You have an array $$$a$$$ consisting of $$$n$$$ positive integers. You decide to "condense" this array. In one operation, you can replace any $$$m$$$ elements of the array with a single element consisting of their sum.

For example, if you had the array $$$a = [2, 7, 1, 8, 2, 8]$$$ and $$$m = 3$$$, you could, for example, do the operation on the second, third, and fifth elements, making the array $$$[2, 10, 8, 8]$$$ (note that the order of the array elements doesn't matter for this problem).

Given this information, your task is to figure out the maximum possible largest element in the array that could exist after $$$k$$$ operations.

The first line of input contains three space-separated positive integers $$$n$$$ $$$(1 <= n <= 10^5)$$$, $$$m$$$ $$$(1 <= m <= n)$$$, and $$$k$$$ $$$(1 <= k <= n, k * m <= n)$$$: the length of the array, the number of elements that you can change in a single operation, and the number of operations you can make, respectively.

The next line of input contains the array $$$a$$$ $$$(1 <= a_i <= 10^9)$$$.

Output a single positive integer, representing the maximum possible largest element in the array, after applying exactly $$$k$$$ of the operations described above.

Note that the answer may overflow traditional 32-bit integers.

Full problem: 9 points

6 3 1
2 7 1 8 2 8

23

9 2 3
1 5 4 9 8 6 3 5 7

30