该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

在出完摸金4后，lfq又在想要不要继续出摸金系列的题， 就在lfq还在犹豫的时候，他惊奇的发现，这场招新赛缺少防ak的题，于是，就有了这道摸金5。（其实这场是想出摸金4的，但是因为这场中等题出的差不多了，又缺少防ak，所以摸金4这场就不出了）

问题描述

lfq在疯帽子的茶话会上！有一个由 n 个部分组成的长条蛋糕，每个部分的美味值分别为 $a_1$,$a_2$​,...,$a_n$。茶话会上有 m 个软件ACM成员，不包括lfq。

lfq将把蛋糕切成 m+1 块。形式上，他将蛋糕分成 m+1 个子数组，每个子数组由一些相邻的部分组成。一块蛋糕的美味值是其各部分美味值的总和。然后，他将把这 m+1 块分给 m 个软件ACM成员和他自己（他的那块可以是空的）。然而，每个软件ACM成员只有当其蛋糕块的美味值至少为 v 时才会开心。

lfq希望确保每个软件ACM成员都开心。在这个条件下，他也想最大化他自己那块蛋糕的美味值。你能帮助lfq找到他那块蛋糕的最大可能美味值吗？如果无法确保每个软件ACM成员都开心，输出 -1。
子数组的定义：子数组是指在一个原始数组中，由一个或多个连续的元素组成的序列。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤$10^4$）。测试用例的描述如下。

每个测试用例的第一行包含三个整数 n, m, v（1≤m≤n≤2⋅$10^5$; 1≤v≤$10^9$）— 分别表示组成蛋糕部分的数量、软件ACM成员的数量和其对美味值的最低要求。

下一行包含 n 个空格分隔的整数 $a_1$,$a_2$​,...,$a_n$（1≤$a_i$​≤$10^9$）— 各部分的美味值。

所有测试用例的 n 的总和不超过 2⋅$10^5$。

输出

对于每个测试用例，输出爱丽丝可以获得的蛋糕块的最大美味值，如果无法确保每个生物都开心，则输出 -1。

Samples

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

22
12
2
2
2
0
-1

注意

在第一个测试用例中，lfq可以将第一和第二部分分别作为独立的蛋糕块分配给软件ACM成员，然后自己拿走剩余部分（10+1+1+10=22）的美味值。我们可以证明这是最优解。

在第二个测试用例中，lfq可以将第一和第二部分合并为一块，第六部分作为单独一块分配给软件ACM成员。随后他可以获取剩余部分（10+1+1=12）的美味值。我们可以证明这是最优解。

在第七个测试用例中，lfq无法为每个软件ACM成员分配美味值至少为12的蛋糕块。

Limitation

1s, 1024KiB for each test case.