가랜드

크리스마스 가랜드(전구 장식 줄)를 천장에 매다는 일은 생각보다 까다로운 작업이다. 하나의 가랜드는 길이가 모두 같은 $n$개의 조각으로 이루어져 있으며, 크리스마스 볼 같은 장식 때문에 $i$번째 조각은 저마다의 무게 $w_i$를 가진다.

가랜드는 천장의 $m$개 지점에 고정된다. 맨 앞은 지점 $1$에, 맨 끝은 지점 $m$에 고정되고, 나머지 지점들에도 걸어서 가랜드를 여러 개의 구간(segment) 으로 나눈다. 각 구간은 연속한 몇 개의 조각으로 이루어진다. 장식가는 다음 규칙을 지켜야 한다.

1. 각 구간에 포함된 조각의 개수는 양의 짝수여야 한다. 그래서 각 구간을 정확히 절반씩 두 개의 반구간(half-segment) 으로 나눌 수 있다.
2. 각 반구간에 포함되는 조각은 최대 $d$개까지만 허용된다.
3. 가장 무거운 반구간의 무게를 최소로 만들어야 한다. 반구간의 무게란 그 반구간에 속한 조각들의 무게 합을 말한다.

아래 그림은 12개의 조각을 3개의 구간으로 나누어 최적으로 매단 예시이며, 각 조각의 무게가 원 안에 적혀 있다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에 테스트 케이스의 수 $Z$ ($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$)이 주어진다.

각 가랜드에 대해, 최적으로 매달았을 때 가장 무거운 반구간의 무게를 한 줄에 정수 하나로 출력한다. 규칙 1과 규칙 2를 만족하도록 매다는 것이 불가능하면 대신 BAD를 출력한다.