410231: GYM103987 G Awson Loves Chipmunks

Awson loves chipmunks, especially the $$$k$$$-th one among all $$$n$$$ chipmunks! He wants to keep a consecutive interval of chipmunks in his home, and the interval should include the $$$k$$$-th chipmunk.

However, chipmunks eat a lot and it is a heavy burden for Awson to buy food for all chipmunks. Specifically, the $$$i$$$-th chipmunk has a hunger value $$$a_i$$$. If Awson decides to raise the chipmunks from index $$$l$$$ to $$$r\ (1\le l\le k\le r\le n)$$$, then the burden brought to Awson will be $$$f(l,r)=\sum_{l\le i\le r} a_i$$$.

Awson does not want to worry too much about chipmunks' food, so he will choose the interval with the $$$m$$$-th smallest burden. Now you are required to tell Awson the burden he will carry.

The first line contains three integers $$$n\ (1\le n\le 10^6)$$$, $$$k\ (1\le k\le n)$$$ and $$$m\ (1\le m\le k\,(n-k+1))$$$ as described above.

The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (|a_i|\le 10^9)$$$ represents the hunger value of the $$$i$$$-th chipmunk.

Print an integer representing the $$$m$$$-th smallest burden.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$30$$$ points): $$$n\le 10^3$$$.
• Subtask 2 ($$$70$$$ points): no additional constraints.

4 2 3
1 2 4 8

6

4 2 2
-1 2 -4 8

-2

In the first example, the second chipmunk must be chosen, and there are $$$6$$$ ways to choose the interval in total. They are $$$f(2,2)=2,$$$ $$$f(1,2)=3,$$$ $$$f(2,3)=6,$$$ $$$f(1,3)=7,$$$ $$$f(2,4)=14,$$$ and $$$f(1,4)=15$$$. Among them, $$$f(2,3)=6$$$ is the third smallest, so the answer is $$$6$$$.