Treasure Hunters

Time limit1sMemory limit128 MB

Summary

Assign up to 8 treasures to up to 6 hunters with differing valuations to minimize the gap between the richest and poorest hunter totals.

Level: Medium4 of 10
Topics: Backtracking, Brute force
Solved: No attempts yet

Problem

You have been a treasure hunter for a long time. Disarming traps, slipping past the locals, and walking out with the goods and your skin intact is routine work by now. What makes you sweat is the argument that follows every expedition, when the crew has to split the loot. You have worked with all sorts of people, and nobody ever agrees on what a single piece of treasure is really worth. You need a way to split the haul as fairly as possible.

Input

The input holds a series of data sets, at least 1 and at most 100 of them. No blank line separates one data set from the next.

A single data set has five parts.

Start line. A single line containing START.
Number of treasures. A single line with one integer $t$ , where $1 \le t \le 8$ .
Number of hunters. A single line with one integer $h$ , where $1 \le h \le 6$ .
Treasure value list. $h$ lines, one per hunter in input order: line 1 is hunter 1, line 2 is hunter 2, and so on. Each line holds that hunter's estimated values for treasure 1 through treasure $t$ in that order, separated by spaces. Every hunter estimates every treasure. Each estimate is a positive integer smaller than $10000$ .
End line. A single line containing END.

Output

Print one output set per data set, with exactly one blank line between consecutive output sets.

An output set has one line per hunter, in the same order as the input. Each line lists the treasure numbers that hunter receives in ascending order, then the total value of those treasures as that hunter prices them. All values on a line are separated by spaces. A hunter who receives no treasure gets a line holding only the total 0.

Divide the treasures as fairly as possible. Every treasure goes to exactly one hunter, and no treasure is left over. The fairest division is the one that minimizes the difference between the largest and the smallest of the per hunter totals, so the hunter who feels they got the most and the hunter who feels they got the least end up as close together as possible.

No input has more than one fair division.

Examples2

Example 1

Input

START
5
3
42 500 350 700 100
250 200 500 1000 75
150 400 800 800 150
END
START
5
3
42 500 350 200 100
250 200 500 1000 75
150 400 800 800 150
END
START
5
3
500 500 350 200 100
250 200 500 1000 75
150 400 800 800 150
END

Expected output

Example 2

Input

START
3
2
5 60 7
40 9 80
END

Expected output

1 3 12
2 9