Xiao Qian’s Problem

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Xiao Qian is a beautiful and clever girl in our ACM team.So many boys fall in love with her.They are all handsome.Now Xiao Qian wants to choose one from them.She wanted to choose the one who can make much money in the future.She designs a problem as follow. In the N*N(0≤N≤20) grids,she puts some money in some grids.Xiao Qian is not rich.So she will put at most 100 in every grid.Boys should start from the left-up grid and leave from the right-down grid.And boys can only walk down or walk right.When someone gets one grid,he will get all the money.After that, Xiao Qian will put some money in it.Xiao Qian want her girlfriend a patient one.So she asks the boys walk from left-up to right-down 3 times. Can you calculate the maximum money one can get?

Input

One integer N N*N integers are the initial money in every grid. N*N integers are the money Xiao Qian put after the money be taken in every grid. End of file

Output

Output the maximum money one can get.

Sample Input

4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
1 1 1 1 
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output

43

Hint

My English is so poor.It’s not easy for me to write in English.This problem is not so hard.Please AC it.

Source

DouYufeng&ShenYuliang

提交代码