CSES - TCR Contest - Movies
  • Time limit: 1.00 s
  • Memory limit: 512 MB

You want to watch n movies, each movie exactly once. There are n movie theatres and you want to visit each of them exactly once.

You know the price for watching each movie in each theatre. What is the minimum total price?

Input

The first line contains one integer n.

Then there are n lines, each containing n integers. Each line gives the prices of the movies in a theatre.

Output

Output the minimum total price.

Constraints

  • 1 \le n \le 100
  • each price is between 1 and 1000

Example

Input:

3
2 4 1
5 1 2
2 1 5

Output:

4

Explanation: you can watch movie 1 in theatre 3 (price 2), movie 2 in theatre 2 (price 1) and movie 3 in theatre 1 (price 1).