Professor Utonium has made an amazing discovery and has managed to create the most wonderful pets, which he named crocobauzers. The professor experimentally created N crocobauzers and intends to let them reproduce for a year and the offer them to his friends.
After a lot of study on the N crocobauzers, the professor has discovered that any pair can reproduce and, more so, he actually knows how many cubs a pair will have in a year. Obviously, if the professor would keep the crocobauzers in the same room all the pairs would reproduce and at the end of the year he would have the maximum number of cubs. Unfortunately, this is not possible because the rooms are too small and if he were to put all the crocobauzers in one room they would die. Still, it seems that two rooms are large enough to keep them. After the professor divides the crocobauzers they will stay like that until the end of the year, and any two crocobauzers from the same room will mate.

Task

If you want to have a crocobauzer yourself you have to help the professor divide the crocobauzers so that by the end of the year he has a maximum number of crocobauzer cubs.

Input Data

Line one of input file croco.in contains positive integer N representing the number of crocobauzers.
The following N lines each contain N positive integers separated by spaces; the j-th number of the i-th line represents the number of cubs crocobauzers i and j would have if they were in the same room; obviously, if i equals j the value is 0, and if j is smaller than i the value is equal to the i-th value on line j.

Output Data

Output file croco.out will contain on line one the maximum number of crocobauzers which the professor can have at the end of the year, as well as the number of crocobauzers from the first room, separated by a space. The second line will contain the identification numbers of the crocobauzers from the first room, each separated by a space.

• 2 < N < 111
• 0 < number of crocobauzers from one room < N
• 0 <= the number of cubs of a pair of crocobauzers < 222

Example

5
0 4 1 1 0
4 0 0 0 1
1 0 0 4 0
1 0 4 0 4
0 1 0 4 0

Time limit: 1 second/test

Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
mailto:f.dan.ionut@gmail.com