爱丽丝参加了疯帽子的茶会!有一个长片蛋糕,由 $$$n$$$ 部分组成,味道值为 $$$a_1、a_2、\ldots、a_n$$$。茶会上有 $$$m$$$ 生物,但不包括爱丽丝。
Alice 会将蛋糕切成 $$$m + 1$$$ 块。正式来说,她会将蛋糕划分为 $$$m + 1$$$ 子数组,其中每个子数组由一定数量的相邻部分组成。一块的美味是其各个部分的美味的总和。之后,她会将这些 $$$m + 1$$$ 碎片分配给 $$$m$$$ 生物和她自己(她的碎片可以是空的)。然而,每个 $$$m$$$ 生物只有在其作品的美味达到 $$$v$$$ 或更高时才会感到高兴。
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$$$。
示例
输入 #1
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
输出 #1
22 12 2 2 2 0 -1
注意
对于第一个测试用例,Alice 可以将第一部分和第二部分作为自己的部分,然后将剩余的 $$$10 + 1 + 1 + 10 = 22$$$ 美味留给自己。我们可以证明她不能做得更好。
对于第二个测试用例,Alice 可以将第一部分和第二部分作为一个部分给出,并将第六部分作为一个部分给出。然后她可以将剩余的 $$$10 + 1 + 1 = 12$$$ 美味留给自己。我们可以证明她不能做得更好。
对于第七个测试用例,Alice 无法给每个生物一块至少 $$$12$$$ 的美味。