1534: Green

圣诞节就要到了。现在有个困难的任务摆在你眼前――装饰房间。

    你手头上有n朵大小相同的花，第i朵花的重量为w_i。现在打算用一根绳将这n朵花按顺序穿起来，挂在天花板上。绳子被m个点固定，也就是绳子的一头被固定在1号点，另外一头固定在m号点，中间部分需要固定在剩余的点。当然，装饰还有一些规则要注意：

（i）           每一段需要包含非0的偶数个花朵。正因如此，我们可以将每一段划分为两个半段。

（ii）       为了减小你的客人撞到花环的可能，花环不能挂的太低：也就是说，每个半段不能超过d朵花。

（iii）    最后，你需要让所有半段的重量的最大值最小。

下图是一个不错的安排方案，圈中的数字代表花朵的重量

输入的第一行包含一个正整数z（z ≤ 20），代表测试数据的组数。

    对于每组测试数据，第一行包含三个正整数n，m和d（1 ≤ n ≤ 15000,2 ≤ m ≤ 10000，1 ≤ d ≤ 2000，且n*d ≤ 5000000）。接下来一行包含n个正整数w₁，w₂，…，w_n（1 ≤ w_i ≤ 10000），代表对应花的重量。

4
4 3 10
10 10 20 20
6 4 10
1 1 100 100 1 1
6 3 10
1 1 100 100 1 1
1 2 2
333

20
100
200
BAD