Garlands

Time limit2sMemory limit512 MB

Summary

Split a weighted sequence of n pieces into m segments of even length, each half-segment at most d pieces, minimizing the maximum half-segment weight.

Level: Hard8 of 10
Topics: Binary search, Dynamic programming, Greedy, Prefix sum
Solved: No attempts yet

Problem

Hanging Christmas garlands is a surprisingly demanding job. A garland consists of $n$ pieces of equal length. Because of decorations such as Christmas balls, piece $i$ has its own weight $w_i$ .

The garland is attached to the ceiling at $m$ spots. Its very beginning is attached to spot $1$ and its end to spot $m$ . It is also hooked to the remaining spots, which splits it into segments, each made of several consecutive pieces. Every decorator must respect the following rules.

Each segment must contain a positive even number of pieces. Because of this, every segment can be split into two equal half-segments.
Each half-segment may contain at most $d$ pieces.
The weight of the heaviest half-segment must be minimized. The weight of a half-segment is the sum of the weights of the pieces it contains.

The picture below shows one optimal hanging of a garland with twelve pieces in three segments; the weight of each piece is written inside its circle.

Input

The first line contains a positive integer $Z$ ( $Z \le 50$ ), the number of test cases. Then $Z$ test cases follow.

Each garland is described by two lines. The first line contains three positive integers $n$ , $m$ , and $d$ ( $1 \le n \le 40000$ , $2 \le m \le 10000$ , $1 \le d \le 10000$ ), as described above. The second line contains $n$ positive integers $w_1, w_2, \dots, w_n$ ( $1 \le w_i \le 10000$ ), the weights of the pieces.

Output

For each garland, output a single line with one integer: the weight of the heaviest half-segment in an optimal attachment. If it is impossible to hang the garland while satisfying rules 1 and 2, output the word BAD instead.

Examples2

Example 1

Input

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

Expected output

20
100
200
BAD

Example 2
Input
```
1
2 2 1
5 7
```
Expected output
```
7
```