Given a cube $A$ of size $n \times n \times n$. On cell $(x, y, z)$ written an integer $A_{x, y, z}$.
From $(x, y, z)$, you can reach $(x', y', z')$ if $|x-x'|+|y-y'|+|z-z'|=1$.
You are currently standing at $(1, 1, 1)$. Find the shortest cost to reach $(n, n, n)$ knowing that moving to cell $(i, j, k)$ costs you $A_{i, j, k}$.
### Input
- The first line contains an integer $n$.
- The next $n \times n$ lines, the $i^{th}$ line contains $n$ integers $A_{\lfloor \frac{i - 1}{n} + 1 \rfloor, (i - 1) \mod n + 1, k}$. In other words, the first group of $n$ lines is the matrix $A_{1, j, k}$, the second group of $n$ lines is the matrix $A_{2, j, k}$ and so on...
### Output
- Print the weight of the shortest path from $(1, 1, 1)$ to $(n, n, n)$.
### Constraints
- $1 \le n \le 100$.
- $1 \le A_{i, j, k} \le 1000$.
### Example
Input:
```
2
1 2
3 1
3 3
1 2
```
Output:
```
5
```
#### Note:
- Moving from $(1, 1, 1)$ to $(1, 1, 2)$ cost $2$.
- Moving from $(1, 1, 2)$ to $(1, 2, 2)$ cost $1$.
- Moving from $(1, 2, 2)$ to $(2, 2, 2)$ cost $2$.