C. Alice's Adventures in Cutting Cake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of $$$n$$$ sections with tastiness values $$$a_1, a_2, \ldots, a_n$$$. There are $$$m$$$ creatures at the tea party, excluding Alice.

Alice will cut the cake into $$$m + 1$$$ pieces. Formally, she will partition the cake into $$$m + 1$$$ subarrays, where each subarray consists of some number of adjacent sections. The tastiness of a piece is the sum of tastiness of its sections. Afterwards, she will divvy these $$$m + 1$$$ pieces up among the $$$m$$$ creatures and herself (her piece can be empty). However, each of the $$$m$$$ creatures will only be happy when the tastiness of its piece is $$$v$$$ or more.

Alice wants to make sure every creature is happy. Limited by this condition, she also wants to maximize the tastiness of her own piece. Can you help Alice find the maximum tastiness her piece can have? If there is no way to make sure every creature is happy, output $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n, m, v$$$ ($$$1\le m\le n\le 2\cdot 10^5$$$; $$$1\le v\le 10^9$$$) — the number of sections, the number of creatures, and the creatures' minimum requirement for tastiness, respectively.

The next line contains $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the tastinesses of the sections.

The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the maximum tastiness Alice can achieve for her piece, or $$$-1$$$ if there is no way to make sure every creature is happy.

Example
Input
7
6 2 1
1 1 10 1 1 10
6 2 2
1 1 10 1 1 10
6 2 3
1 1 10 1 1 10
6 2 10
1 1 10 1 1 10
6 2 11
1 1 10 1 1 10
6 2 12
1 1 10 1 1 10
6 2 12
1 1 1 1 10 10
Output
22
12
2
2
2
0
-1
Note

For the first test case, Alice can give the first and second section as their own pieces, and then take the remaining $$$10 + 1 + 1 + 10 = 22$$$ tastiness for herself. We can show that she cannot do any better.

For the second test case, Alice could give the first and second section as one piece, and the sixth section as one piece. She can then take the remaining $$$10 + 1 + 1 = 12$$$ tastiness for herself. We can show that she cannot do any better.

For the seventh test case, Alice cannot give each creature a piece of at least $$$12$$$ tastiness.