The usual stuff, after you beat the boss at the topmost floor of his castle, the evil boss triggers the auto destruct function of his castle, and you must escape! However, not so fast! You have fought really bravely and it seems you do deserve some rewards. There are N floors in the castle, and there are treasures lying about in the castle, you want to escape and get as much treasure as you can. Each piece of treasure has a value, and you would want to maximize the sum. With the auto destruction of the castle imminent, the exit stair of floor i will crumple after Ti minutes (it's still open at the Ti-th minute), you do not want to left buried in the castle, so you have to leave the i-th floor in Ti-th minute.
Input
The first line of the input is T (T≤100), the number of testcases. Then T blocks follow, each has the form: an integer N (N≤100), the number of floors. Integers X, Y, your initial position on the N-th floor. Then N lnteger pairs, each being the Xi and Yi, coordinate of the stairs of the i-th floor, then N lines follow each with the form: an integer Mi (0≤Mi≤5), the number of treasure of the i-th floor. Then Mi triples follow, each being a piece of treasure's X and Y coordinate and it's value. Then N integers, the i-th is Ti (Ti ≤ 1200). All the input above are given in the order of N to 1. All coordinates are in range [-1200,1200].
Output
The maximum value you can get or "I'm doomed, though I fought bravely" if you cannot escape. Assume you can only go X and Y direction and your speed is 1 unit per minute.
Sample Input
1
1
0 0
10 10
1 4 5 10
1000
Sample Output
10
https://www.nowcoder.com/questionTerminal/9b230d30fedd4b1ba2548ce01c00ff0d