2014
01-04

# I can do it better

ACboy is playing a new stone game. There’s a rectangular grid board, and some stones placed at the initial location Bi(Xi, Yi) and the targets are at the location Si(Pj, Qj), the time that moving between them is Di,j = |Xi – Pj| + |Yi – Qj| + 1 minutes. And at different places may have different stones, and different target places have different capacity. In the following picture, B1,2,3 stands for the initial places, S1,2,3,4 stands for the target places. In detail, B1(5) means there are 5 stones at this location, S2(4) means you can move at most 4 stones to this target location.

The one who moves the stones from the initial places to the target places using less time will win. So ACboy now telling you his play plan, and you should tell hime whether his plan is the best, or he can do it better.

The input file consists of The game board description and the play plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 <= N <= 100) is a number of initial places(numbered from 1 to N). M (1 <= M <= 100) is a number of target places(numbered from 1 to M).

The following N lines describe initial places. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 <= Xi, Yi <= 1000) are the coordinates of initial places, and Bi (1 <= Bi <= 1000) is the number of stones at this location.

The description of initial places is followed by M lines that describe target places. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 <= Pj, Qj <= 1000) are the coordinates of the target places, and Cj (1 <= Cj <= 1000) is the capacity of this place.

The description of the play plan follows on the next N lines. The play plan of ith initial place consists of M integer numbers Ei,j separated by spaces. Ei,j (0 <= Ei, j <= 1000) is a number of stones that shall move from the ith initial place to the jth target place.

The plan in the input file is guaranteed to be valid. Namely, B1+B2+….+Bn <= S1+S2+….+Sn.

Process to the end of file.

The input file consists of The game board description and the play plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 <= N <= 100) is a number of initial places(numbered from 1 to N). M (1 <= M <= 100) is a number of target places(numbered from 1 to M).

The following N lines describe initial places. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 <= Xi, Yi <= 1000) are the coordinates of initial places, and Bi (1 <= Bi <= 1000) is the number of stones at this location.

The description of initial places is followed by M lines that describe target places. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 <= Pj, Qj <= 1000) are the coordinates of the target places, and Cj (1 <= Cj <= 1000) is the capacity of this place.

The description of the play plan follows on the next N lines. The play plan of ith initial place consists of M integer numbers Ei,j separated by spaces. Ei,j (0 <= Ei, j <= 1000) is a number of stones that shall move from the ith initial place to the jth target place.

The plan in the input file is guaranteed to be valid. Namely, B1+B2+….+Bn <= S1+S2+….+Sn.

Process to the end of file.

2 1
0 0 5
1 1 5
2 2 5
5
0

I can do it better

Hint: in the case, ACboy moves the 5 stones from B1 at (0,0) to S1 at (2,2), and it costs him 5*5 = 25 minutes,
but if he move the 5 stones from B2 at (1,1) to S1 at (2,2), it will only takes him 3*5 = 15 minutes, so his plan is not the best.

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法