Minimum Gold to Win on a Grid

You are given a square grid of size (N \times N). The top-left cell is ((1,1)) and the bottom-right cell is ((N,N)). Each cell ((i,j)) has two associated costs: (a_{i,j}) and (b_{i,j}). From any cell ((i,j)), you can perform the following moves any number of times (as long as the destination cell is within the grid):

• Move right (to \((i,j+1)\)) at a cost of \(a_{i,j}\) coins.
• Move down (to \((i+1,j)\)) at a cost of \(b_{i,j}\) coins.

You win the game if you reach any cell \((x_0,y_0)\) such that the Manhattan distance to \((N,N)\) is at most 2, i.e., \[ |x_0 - N| + |y_0 - N| \le 2. \]
Starting from \((1,1)\) with an unlimited amount of gold, determine the minimum number of coins required to win the game.

inputFormat

The input consists of the following:

• The first line contains an integer \(N\), the size of the grid.
• The next \(N\) lines each contain \(N\) integers. The \(j\)-th integer in the \(i\)-th line represents \(a_{i,j}\), the cost to move right from cell \((i,j)\). (Note: For cells in the last column, this cost may be provided but will not be used.)
• The following \(N\) lines each contain \(N\) integers. The \(j\)-th integer in the \(i\)-th line represents \(b_{i,j}\), the cost to move down from cell \((i,j)\). (Note: For cells in the last row, this cost may be provided but will not be used.)

outputFormat

Output a single integer representing the minimum amount of coins required to reach any cell ((i,j)) such that (|i - N| + |j - N| \le 2).

sample

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

3