Minimizing the Product of Cost and Impact in Grid City

B City can be regarded as an \(n \times n\) grid. The prison is located at \((1,1)\) and the only exit is at \((n,n)\). Every two adjacent vertices (i.e. vertices whose coordinates differ by exactly one in Manhattan distance) are connected by an undirected road (diagonal roads are not allowed). You are assigned to set up defenses on some roads such that no matter how zbw chooses a path from \((1,1)\) to \((n,n)\), he will have to go through at least one defended road.

For a horizontal road connecting \((i,j)\) to \((i,j+1)\), the cost to defend it is \(r_{i,j}\) and it has an impact of \(x_{i,j}\) on the people. For a vertical road connecting \((i,j)\) to \((i+1,j)\), the cost is \(d_{i,j}\) and the impact is \(y_{i,j}\). If you defend a set of roads \(S\), let the total cost be \(w = \sum_{e \in S}\) (cost of edge \(e\)) and the total impact be \(e = \sum_{e \in S}\) (impact of edge \(e\)). Your goal is to choose a defending set \(S\) (which forms an s-t cut separating \((1,1)\) from \((n,n)\)) so that the product \(w \times e\) is minimized.

Hint: In a grid, every s-t cut that separates \((1,1)\) from \((n,n)\) corresponds to a staircase (monotone) path from \((1,1)\) to \((n,n)\) in the dual grid. For each move right you incur \(r_{i,j}\) and \(x_{i,j}\) (for some appropriate \(i,j\)), and for each move down you incur \(d_{i,j}\) and \(y_{i,j}\). Thus, the problem reduces to finding a monotone path from the top‐left to the bottom‐right of the grid such that if \(w\) is the sum of monetary costs and \(e\) is the sum of impacts along this path then the product \(w\times e\) is minimized.

inputFormat

The first line contains an integer \(n\) (the number of rows/columns in the grid).
Then follow \(n\) lines, each containing \(n-1\) space-separated integers, representing the horizontal road defense costs \(r_{i,j}\) (for \(1 \leq i \leq n,\ 1 \leq j \leq n-1\)).
Then \(n\) lines follow, each containing \(n-1\) space-separated integers, representing the corresponding impacts \(x_{i,j}\).
Next, there are \(n-1\) lines, each containing \(n\) space-separated integers, representing the vertical road defense costs \(d_{i,j}\) (for \(1 \leq i \leq n-1,\ 1 \leq j \leq n\)).
Finally, there are \(n-1\) lines, each containing \(n\) space-separated integers, representing the impacts \(y_{i,j}\) for vertical roads.

outputFormat

Output a single integer – the minimum possible value of \(w \times e\) for an s-t cut (defended roads) such that any path from \((1,1)\) to \((n,n)\) encounters at least one defended road.

sample

2
1
2
1
1
2 3
1 1

8