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?
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