Por XIII Maratona de Programação IME-USP, 2009 Brazil
We are in the year 2931. Scientists detected a meteor that, in 15 months, will collide with the Earth and extinguish the life on planet. There is no remaining time to prepare offensives against the meteor, so we can only make our last wishes and wait for the collision.
A group of people decided to meet and make the last wish of hundreds of thousands of people: see the team Portuguesa win the South America Libertadora's Cup. For such, they will need to hire several skilled players, that are also expensive.
To do that, they studied the personality of the best players in the world, and reached the conclusion that some would accept to play at Portuguesa easily (that is, they would be hired for a less price) if they realized that they would be the only “stars” in the team. Others, would come easily if they realized that Portuguesa already had others stars.
This way, through a more detailed study of the personalities, they managed to define, for each player, which would be the price to hire them in several scenarios.
For example, the player X could be hired for $3 if he was the only star of the team, or $5 if there was one star on the team before he entered. On the other hand, the player Y would be hired for $4 if he was the only star of the team, or $2 if there was one star on the team.
In this scenario, the best way to hire X and Y would be to first hire the player X by $3 and then hire Y by $2, spending a total of $5.
You will receive the data of the costs of hiring the players in each scenario, and must say how much the Portuguesa's supporters will have to save to build a dream team and win the Libertadores.
The input has several instances.
The first row contains an integer N (2 ≤ N ≤ 18), representing the quantity of players to be hired. Each of the next N rows represents a player. Each row contains N integers c0, c1, c2, …, cN-1 (1 ≤ ci ≤ 1000, for all 0 ≤ i < N) separated by spaces, where c k represents the cost to hire the player c if k players are already hired.
The input ends when N = 0.
For each input instance, print one row with an integer representing the minimum amount of money that they will have to spend to hire the N players.
|Sample Input||Sample Output|