Given a matrix $A$ of size $n \times n$. Each cell contains a digit from $1$ to $9$.
Find the lowest cost to move from $(1, 1)$ to $(n, n)$, knowing that moving to cell $(i, j)$ costs $A_{i, j}$.
### Input
- The first line contains an integer $n$.
- The next $n$ lines represents $A$, each line contains a digit string of length $n$.
### Output
- Print the lowest cost.
### Constraints
- $1 \le n \le 5000$.
### Example
Input:
```
3
312
291
124
```
Output:
```
8
```
#### Note: Optimal path $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) $.
