There are n cities. Going from city i to city j cost Ai,j coins. Find the minimum cost route that visits each city exactly once and returns to the starting city.
### Input
- The first line contains integers n.
- Next n lines, ith line contains n integers Ai,j.
### Output
- A single integers is the minimum cost.
### Constraints
- 1≤n≤10
- 1≤Ai,j≤1000
### Example
Input:
502851100599350662820263870
Output:
17
