花环装饰是一项最近变得越来越重要的职业，特别是在圣诞节期间。任何孩子都可以装饰圣诞树，任何父母都可以把礼物插进插座，甚至任何人都可以开始相信圣诞老人，但悬挂圣诞花环完全是另一回事。正如你将了解到的，这是一项极其重要、充满责任感且艰巨的工作。

一个花环由 $n$ 个等长的部分组成。由于花环上挂有圣诞球等装饰物，第 $i$ 个部分有其自身的重量 $w_i$。花环必须固定在天花板上的 $m$ 个固定点上，其中花环的起点应固定在第 1 个点，终点固定在第 $m$ 个点。花环还应挂在其余的固定点上，这将其分成了若干个片段（segment），每个片段由若干个连续的部分组成。然而，每一位受人尊敬的花环装饰师都应该牢记以下几条规则：

• (i) 每个片段应包含正偶数个部分。由于这个条件，我们可以将一个片段平分为两个半片段（half-segment）。
• (ii) 为了尽量减少客人用头撞到你珍贵的花环（并将其撕碎）的机会，花环不能挂得太低：每个半片段最多只能包含 $d$ 个部分。
• (iii) 最后，为了防止天花板塌落到人们的头上，装饰师应该使最重的半片段的重量最小化。

下面展示了一个最优悬挂花环的示例（由三个片段中的十二个部分组成）；圆圈中给出了各个部分的重量。

最优悬挂花环的示例（由三个片段中的十二个部分组成）；圆圈中给出了各个部分的重量

输入包含多个测试用例。输入的第一行包含一个正整数 $Z \le 50$，表示测试用例的数量。接下来是 $Z$ 个测试用例，每个测试用例都符合下面“输入格式”中所述的格式。对于每个测试用例，你的程序需要输出符合下面“输出格式”中所述格式的内容。

输入格式

每个花环的描述由两行组成。

第一行包含三个正整数 $n$、$m$ 和 $d$（$1 \le n \le 40000$，$2 \le m \le 10000$，$1 \le d \le 10000$），由单个空格分隔，其含义如上所述。

第二行包含 $n$ 个正整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10000$），表示对应部分的重量。

输出格式

对于每个花环，你的程序应该输出单行，包含一个整数，表示在花环的最优悬挂方案中，最重半片段的重量。

如果无法在满足条件 (i) 和 (ii) 的情况下悬挂花环，则你的程序应该输出单词 BAD。

样例

输入样例 1

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

输出样例 1

20
100
200
BAD