# Let the light guide us

Description

Plain of despair was once an ancient battlefield

where those brave spirits had rested in peace for thousands of years.

Actually no one dare step into this sacred land until the rumor that

“there is a huge gold mine underneath the plain” started to spread.

Recently an accident destroyed the eternal tranquility. Some greedy

fools tried using powerful bombs to find the hidden treasure. Of

course they failed and such behavior enraged those spirits–the

consequence is that all the human villages nearby are haunted by

ghosts.

In order to stop those ghosts as soon as possible, Panda the Archmage

and Facer the great architect figure out a nice plan. Since the plain

can be represented as grids of N rows and M columns, the plan is that

we choose ONLY ONE cell in EACH ROW to build a magic tower so that

each tower can use holy light to protect the entire ROW, and finally

the whole plain can be covered and all spirits can rest in peace

again. It will cost different time to build up a magic tower in

different cells. The target is to minimize the total time of building

all N towers, one in each row.

“Ah, we might have some difficulties.” said Panda, “In order to

control the towers correctly, we must guarantee that every two towers

in two consecutive rows share a common magic area.”

“What?”

“Specifically, if we build a tower in cell (i,j) and another tower in

cell (i+1,k), then we shall have |j-k|≤f(i,j)+f(i+1,k). Here, f(i,j)

means the scale of magic flow in cell (i,j).”

“How?”

“Ur, I forgot that you cannot sense the magic power. Here is a map

which shows the scale of magic flows in each cell. And remember that

the constraint holds for every two consecutive rows.”

“Understood.”

“Excellent! Let’s get started!”

Would you mind helping them?

Input There are multiple test cases.

Each test case starts with a line containing 2 integers N and M

(2<=N<=100,1<=M<=5000), representing that the plain consists N rows

and M columns.

The following N lines contain M integers each, forming a matrix T of

N×M. The j-th element in row i (Tij) represents the time cost of

building a magic tower in cell (i, j). (0<=Tij<=100000）

The following N lines contain M integers each, forming a matrix F of

N×M. The j-th element in row i (Fij) represents the scale of magic

flows in cell (i, j). (0<=Fij<=100000）

For each test case, there is always a solution satisfying the

constraints.

The input ends with a test case of N=0 and M=0.

Output For each test case, output a line with a single integer, which

is the minimum time cost to finish all magic towers.

- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答

*1*条回答

#### 为你推荐

- Let the light guide us
- matrix
- 1个回答