
ZOJ Problem Set  3431
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 T_{i} minutes (it's still open at the T_{i}th minute), you do not want to left buried in the castle, so you have to leave the ith floor in T_{i}th minute. InputThe 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 Nth floor. Then N lnteger pairs, each being the X_{i} and Y_{i}, coordinate of the stairs of the ith floor, then N lines follow each with the form: an integer M_{i} (0≤M_{i}≤5), the number of treasure of the ith floor. Then M_{i} triples follow, each being a piece of treasure's X and Y coordinate and it's value. Then N integers, the ith is T_{i} (T_{i} ≤ 1200). All the input above are given in the order of N to 1. All coordinates are in range [1200,1200]. OutputThe 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 Input1 1 0 0 10 10 1 4 5 10 1000 Sample Output10 Author: SONG, Yu Contest: ZOJ Monthly, November 2010 