2423. iDOL M@STER

单点时限: 3.0 sec

内存限制: 256 MB

n idols are belonging to the Maximum Production. Now, the president of the Maximum Production decided to split these n idols into m groups of trio, duo, or solo, and maximize the total charm of these groups. If a group is solo, the charm of the group should be the charm of the idol. If a group is duo, the charm is calculated by the formula shown below. In the formula, a1 and a2 mean the charm of each idol and c means the congeniality between the idols.

  • (a1 + a2) * (1 + ((c - 50) / 50)3 )

If a group is trio, the charm is calculated by the formula shown below. In the formula, a1 , a2 and a3 mean the charm of each idol and c1,2 ,c1,3 and c2,3 mean the congeniality between first idol and second idol, first idol and third idol, second idol and third idol respectively.

  • (a1 + a2 + a3) * (1 + ((c1, 2 + c1, 3 + c2, 3 - 140) / 140)3 )

You are a producer employed by Maximum Production and your job is to write a program to maximize the total charm of groups. If there are two or more such set of groups, you can choose any of them.

输入格式

Input consists of multiple test cases. The first line of each test case contains two positive integers n ( n <= 18 ), m ( n/3 <= m <= n ). The following n lines contain information about n idols, and their i-th line contains one name namei and single positive integer ai(ai <= 100), indicating the name and the charm of i-th idol respectively. The following n - 1 lines contain information about compatibilities, and their i-th line contains n - i positive integers indicating information about compatibilities between i-th idol and others. The j-th integer ci, j (ci, j <= 100 ) indicates the congeniality between i-th idol and i +j -th. Input is terminated by a case of n = m = 0, and it should not be processed.

You can assume that there is no idol ot the same name, and the name consists of at most 100 alphabets.

输出格式

For each test case, you should output a test case number C starting from 1 in the format “Case #C”. For the following m lines, you should output a group to each line in non-increasing order of the charm of the group. In case of output for duo or trio, you should output their name in ASCII code ascending order and separate them by single space character. If there are two or more groups with the same charm, first, you should output a group that the smallest idol in ASCII code ascending order belongs to. You should output a blank line between test cases.

样例

Input
11 8
Haruka 83
Chihaya 72
Yukiho 80
Yayoi 72
Ritsuko 85
Azusa 91
Iori 77
Makoto 73
Ami 74
Mami 74
Miki 84
10 80 10 10 10 80 10 10 10 10
10 10 10 10 10 10 10 10 10
10 10 10 80 10 10 10 10
10 10 10 10 10 10 10
10 10 10 10 10 10
10 10 10 10 10
10 10 10 10
10 10 10
100 10
10
0 0
Output
Case #1
Haruka Iori Yukiho
Ami Mami
Azusa
Ritsuko
Miki
Makoto
Chihaya
Yayoi

0 人解决,1 人已尝试。

0 份提交通过,共有 2 份提交。

9.9 EMB 奖励。

创建: 12 年,10 月前.

修改: 4 年前.

最后提交: 9 月,4 周前.

来源: International Maximum-Cup 2008

题目标签