CF2028C Alice's Adventures in Cutting Cake

爱丽丝参加了疯帽子的茶话会！有一块长长的蛋糕，由 $n$ 个部分组成，每个部分的美味度值为 $a_1, a_2, \ldots, a_n$ 。茶话会上共有 $m$ 个生物，但不包括爱丽丝。 爱丽丝将把蛋糕切成 $m + 1$ 块。正式地说，她将把蛋糕分成 $m + 1$ 个子串，每个子串由一定数量的相邻部分组成。一块蛋糕的美味度是其各部分美味度的总和。之后，她会将这些 $m + 1$ 块蛋糕分给 $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$ 美味度的部分。