Garlands

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.

1. Each segment must contain a positive even number of pieces. Because of this, every segment can be split into two equal half-segments.
2. Each half-segment may contain at most $d$ pieces.
3. 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.

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.

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.