E. Food Allocation I
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After a local forest tour gone wrong, you and $$$n$$$ other survivors have been stranded in the wilderness. Due to your incredible leadership skills, you have taken command of the rest of the survivors and need to organize them in order to get the necessary supplies to survive.

There are $$$n$$$ different types of food that each of the $$$n$$$ survivors can collect. Each survivor can collect any of the types of food, but they each have different skill levels at collecting each type of food, which represent the amount of that food that they can collect.

You must assign each survivor to a single food type and ensure that your camp has a survivor assigned to each food type to maximize the value of the food you get. In this case, you and the survivors all pool together the collected food, so the value of the assignment is the sum of all the food collected by each survivor. How do you maximize this assignment of survivors?

Input

The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 10$$$) giving the number of survivors. The next $$$n$$$ lines will each consist of $$$n$$$ integers where the $$$j$$$th integer on the $$$i$$$th line, $$$s_{ij}$$$ ($$$0 \leq s_{ij} \leq 10^5$$$), gives the skill point value for survivor $$$i$$$ when it is assigned food type $$$j$$$.

Output

Output a single integer giving the total value of the optimal assignment of survivors to tasks.

Example
Input
2
3 4
0 2
Output
5
Note

For the sample, it is optimal to make the first survivor do the first task and the second survivor do the second task, which leads to a total value of $$$3 + 2 = 5$$$.