Asylum patients: let's arrange something for us three
In certain country attempts to reduce alcohol consumption lead to restriction on selling strong drinks in amounts smaller than half-litre. Such a volume is considered too much for a single person to casually apply after the work on a way home.
However citizens of that country were quite social and inventive - and this led to tradition of gathering in groups of three. They buy "half-litre" of their favorite liquid and sit drinking and talking calmly, wisely and happily even despite being quite strangers just an hour ago. This way plumber can exchange thoughts with professor and musician with engineer. Though everyone may have one's own preferences!
This leads us to the problem similar to Dancing Pairs - though now it is about "triplets" and situation is gender-insensitive.
Problem Statement
Given a group of people (divisible by 3) we want to arrange them into groups of 3 in such a way that
happiness is maximized. For this we ask each person and find out how much happiness each two of them feel if
they are arranged into the same group. Obviously this is, in turn, sum of their personal happiness towards each
other. E.g. if person X feels pXY happiness if put into group with Y and at the same time person Y feels
pYX happiness because of being in the group with X - we simply count the total for the pair:
p(X, Y) = p(Y, X) = pXY + pYX
And the total for the group is of course:
p(X, Y, Z) = p(X, Y) + p(X, Z) + p(Y, Z)
Regretfully author of the problem doesn't know how to solve it :) So you are simply asked to find arrangement which gives more happiness than some "good" number achieved by author's algorithm (secret).
Input
First line contains values N and G - total number of people and lower limit of happiness which needs to be
exceeded by your solution.
Then N-1 lines follow. The first contains single value p(0, 1). The second contains two values p(0, 2) and
p(1, 2). The last line contains values from p(0, N-1) to p(N-2, N-1).
Answer
Output persons identified by their numbers from 0 to N-1 in single line, such that if it is split into
triplets, it produces the required arrangement.
Example
input:
9 575
25
67 64
70 29 42
41 73 27 32
64 4 72 35 35
67 71 40 20 52 53
24 42 67 69 57 47 64
17 64 51 56 76 69 8 61
answer:
0 5 2 6 4 1 8 7 3
Let's check: in the first group happiness is 64 + 67 + 72 = 203, in the second 73 + 71 + 52 = 196, in the
third 69 + 56 + 61 = 186. Total is 585 - slightly exceeding limit of 575.