Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3431

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.


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].


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

0 0
10 10
1 4 5 10

Sample Output


Author: SONG, Yu
Contest: ZOJ Monthly, November 2010
Submit    Status