Ms. Magda likes cookies very much. In the summer she decided to organise an expedition which purpose is to taste wares from each bakery. Our heroine has been thinking about finding as minimal as possible lenght of the track which passes through each bakery exactly once and returns do the start point. She managed to get the table of distances beetween every two bakeries. You, as a good friend of Magda, decided to help her with the problem and here is our purpose: you have to write a program, which calculates a minimal lenght of the track in exchange for cookies. The shorter your track is, the more cookies you get and Magda is more satisfacted. Don't dissapoint her, she's pretty hot.

Example 

We've got 4 bakeries: 1,2,3,4.

The table of distances looks as follows:

The shortest lenght equals to:18.

An example way how the track may look:1->4->3->2->1

Input

In the first line the number of bakeries (n).

Next follow n lines, each consisted of n numbers (which are the distances beetween bakeries).

Output

In the first line the calculated lenght of your track. In the second line n+1 numbers separated by whitespaces (from 1 to n including) where the first and the last have to be the same, it's the order of visiting bakeries.

n<=400

Example

Input:
4
0 4 7 3
4 0 5 8
7 5 0 6
3 8 6 0
Output:
18
1 4 3 2 1

Score:

It's the number of cookies that Magda gives to you, she gives more if the track is shorter.