CF2028C Alice's Adventures in Cutting Cake

爱丽丝参加了疯帽子的茶话会！有一块长长的蛋糕，由 $n$ 个部分组成，每个部分的美味度值为 $a_1, a_2, \ldots, a_n$ 。茶话会上共有 $m$ 个生物，但不包括爱丽丝。 爱丽丝将把蛋糕切成 $m + 1$ 块。正式地说，她将把蛋糕分成 $m + 1$ 个子串，每个子串由一定数量的相邻部分组成。一块蛋糕的美味度是其各部分美味度的总和。之后，她会将这些 $m + 1$ 块蛋糕分给 $m$ 个生物和她自己（她的那块蛋糕可以是空的）。但是，只有当每个 $m$ 个生物的蛋糕美味度达到或超过 $v$ 时，它们才会感到高兴。 Alice 想要确保每个生物都快乐。受此条件限制，她还想最大化自己的那块食物的美味程度。你能帮助 Alice 找到她的那块食物可以达到的最大美味程度吗？如果没有办法确保每个生物都快乐，则输出 $-1$ 。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。测试用例的描述如下。 每个测试用例的第一行包含三个整数 $n, m, v$ ( $1\le m\le n\le 2\cdot 10^5$ ; $1\le v\le 10^9$ ) — 分别表示部分数量、生物数量和生物对美味的最低要求。 下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ) — 部分美味程度。 所有测试用例的总和 $n$ 不超过 $2\cdot 10^5$ 。

对于每个测试用例，输出 Alice 可以达到的最大美味程度，或者如果没有办法确保每个生物都开心，则输出 $-1$ 。 ### 样例解释 对于第一个测试案例，爱丽丝可以将第一和第二部分作为自己的部分，然后将剩余的 $10 + 1 + 1 + 10 = 22$ 美味度留给自己。我们可以证明她不能做得更好。 对于第二个测试案例，爱丽丝可以将第一和第二部分作为一个部分，将第六部分作为一个部分。然后她可以为自己拿走剩余的 $10 + 1 + 1 = 12$ 美味度。我们可以证明她不能做得更好。 对于第七个测试案例，爱丽丝不能给每个生物至少 $12$ 美味度的部分。

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.