题目描述

你是一名经验丰富的宝藏猎人，擅长拆除陷阱、避开原住民，并在确保自身安全的情况下获取宝物。这些事情对你来说不算什么，但每次探险后如何公平分配战利品才是最让你头疼的问题。你和各种性格的人合作过，但大家对每件宝物的价值看法总是不一致。你需要找到一种尽可能公平的分配方式。

输入格式

输入包含多组测试数据（最多100组），每组数据格式如下，且数据组之间没有空行分隔：

1. 起始行 - 单行字符串 "START"
2. 宝藏数量 - 单行整数 $t$（$1 \leq t \leq 8$），表示宝藏的数量。
3. 猎人数量 - 单行整数 $h$（$1 \leq h \leq 6$），表示猎人的数量。
4. 宝藏估值列表 - 共 $h$ 行，每行对应一个猎人（第1行是猎人1，第2行是猎人2，依此类推）。每行包含 $t$ 个正整数（严格小于10000），表示该猎人对每件宝藏的估值（第1个数字是宝藏1，第2个数字是宝藏2，依此类推）。
5. 结束行 - 单行字符串 "END"

输出格式

对于每组输入数据，输出一个分配方案，不同组输出之间用空行分隔。

每个分配方案包含 $h$ 行，每行对应一个猎人（顺序与输入一致），格式为：

• 该猎人分到的宝藏编号（按升序排列）
• 该猎人对自己所获宝藏的总估值

分配方案需满足 最公平 的条件，即：

• 所有猎人中 最高总估值 和 最低总估值 的差值最小。
• 保证没有多个同等公平的分配方式。

输入数据 1

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

输出数据 1

4 700
3 5 575
1 2 550

1 4 5 342
3 500
2 400

1 2 1000
4 1000
3 5 950

来源

South Central USA 2001