Marmots’ Transfer

Time Limit: 30000 ms

Memory Limit: 524287 ms

Description

There are many marmots live on the grasslands and they build many holes under the ground. There are N*N holes and they are arranged in a square, there may be an UNDIRECTED path between two adjacent holes.
All those marmots are living in the northwest hole, now the rainy season coming and they have to transfer to the southeast hole, because it is the highest.
Unfortunately, there is a bug in this underground system;these paths are unsubstantial, so that if too many marmots pass one path the path will be destroyed. We call the max marmots can pass a path as p-value. Now give you the p-value of each path, white a program to calculate how many marmots can transfer to the safe place.
example

Input

There are multiply test cases, end by EOF. Each test cases begin with an integer N (2<=N<=2000), means there are N*N holes, then 2*N-1 lines next, the odd line has N-1 integers describe the west-east path; the even line has N integers describe the north-south path. Each integer is no more than 2000 and no less than 0; describe the corresponding p-value of each path, 0 means there is no way between the two holes.

Output

One integer for each case: the number of marmots can transfer to the safe place.

Sample Input

3
2 2
9 0 2
4 0
4 3 2
3 5
4
0 1 2
3 4 5 6
7 8 9
10 1 2 3
4 5 6
7 8 9 0
1 2 0

Sample Output

7
0

Hint

Source

The First ACM-ICPC Nanjing Invitational Tourn

提交代码