Time limit: 30 s
Memory limit: 32 MB
Garland decorator is a profession which recently gained in importance, especially during Christmas time. Any kid can decorate a christmas tree, any parent can put gifts in sockets, and even anyone can start believing in Santa Claus, but hanging christmas garlands is a completely different story. As you will learn, it is an extremely important, responsible and tough job.
A garland consists of pieces of equal length. Due to decorations like christmas balls attached to garlands, piece has its own weight . The garland has to be attached to the ceiling in spots, where the very beginning of the garland should be attached to spot and its end to spot . The garland should also be hooked to the remaining spots, which divides it into segments, each consisting of several consecutive pieces. There are, however, several rules that every respectable garland decorator should keep in mind.
The input contains several test cases. The first line of the input contains a positive integer , denoting the number of test cases. Then test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.
The description of each garland consists of two lines. The first line describing a particular garland contains three positive integers , , and (, , ) separated by single spaces and described above. The second line contains positive integers , , ..., (), being the weights of the corresponding pieces.
For each garland, your program should output a single line containing one integer, being the weight of the heaviest half-segment in an optimal attachment of the garland. If it is not possible to hang the garland satisfying conditions (i) and (ii), then your program should output word BAD.
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