You are given an n by n grid of integers. A falling path starts at any cell in the top row. From a cell in row i, column j it moves to row i+1 at column j-1, j, or j+1 (staying inside the grid). The path ends when it leaves the bottom row.
Return the minimum possible sum of all cells visited by such a path.
Input format
Line 1: an integer n.
Next n lines: each has n space-separated integers.
Output format
A single integer: the minimum falling-path sum (it may be negative).
Constraints
- 1 <= n <= 100
- -1000 <= each cell <= 1000