0 人解决，1 人已尝试。
0 份提交通过，共有 2 份提交。
9.9 EMB 奖励。
单点时限: 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.
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.
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.
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
Case #1 Haruka Iori Yukiho Ami Mami Azusa Ritsuko Miki Makoto Chihaya Yayoi
0 人解决，1 人已尝试。
0 份提交通过，共有 2 份提交。
9.9 EMB 奖励。