- 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).