Minimal Sum of Disparities Partitioning

Yulia works for a metal processing plant in Ekaterinburg which processes ores from the Ural mountains. Every month, the plant receives n shipments of unprocessed ore, and Yulia must partition these shipments into two groups (subsets) so that the sum of their disparities is minimized.

For any pair of shipments i and j (with 1 ≤ i, j ≤ n), a numeric distance d(i, j) is computed; the smaller the distance, the more similar the shipments are. For any subset S ⊆ {1, …, n}, the disparity is defined as:

where if the subset consists of a single shipment, the disparity is 0. The goal is to partition the set of shipments into two non-empty subsets A and B so that:

is minimized. In case of multiple optimal partitions, any one of them can be output.

Input and Output Format: The input consists of an integer n (the number of shipments) followed by an n×n distance matrix. The output should print the minimal sum of disparities on the first line, the indices (1-indexed) of shipments in the first subset (group A) on the second line, and the indices of shipments in the second subset (group B) on the third line.

inputFormat

The first line of input contains an integer n (2 ≤ n ≤ 15), the number of shipments. Each of the next n lines contains n space-separated numbers, where the j-th number in the i-th line represents the distance d(i, j) between shipments i and j. It is guaranteed that d(i, i)=0 for all i, and typically d(i,j)=d(j,i).

outputFormat

Output three lines:

• The first line contains the minimum possible value of D(A) + D(B).
• The second line contains the 1-indexed shipment numbers of the first group, separated by spaces.
• The third line contains the shipment numbers of the second group.

sample

4
0 10 3 4
10 0 5 6
3 5 0 9
4 6 9 0

9
1 3 4
2