题目描述

在标准手机键盘上，字母按如下方式分布在数字键2到9上：

输入字母C需要按数字键2三次（依次显示A-B-C）。输入一个字母所需的按键次数取决于它在对应按键字母列表中的位置。

Flathead电话公司（FTC）正考虑重新排列按键上的字母，以减少输入姓名或发送短信的平均按键次数。字母必须按字母顺序排列在按键上，但每个按键的字母数量可以不同，且可能使用更多按键。FTC拥有多个不同应用场景的字母频率数据库。例如，将字母S从7键移到8键可能有所帮助。需要编写一个程序，给定字母频率和按键数量，返回使平均按键次数最小的字母分配方案。每个按键至少包含1个字母，最多8个字母。

输入

第一行包含整数 (N)（(1 \leq N \leq 1000)），表示测试用例数。
每个测试用例包含三行：

1. 第一行是整数 (K)（(4 \leq K \leq 26)），表示可用按键数。
2. 第二行和第三行各包含13个十进制数，依次表示字母A-Z的频率百分比。

输出

对每个测试用例，输出一行，包含：

• 数据集编号（从1开始）；
• 最小平均按键次数（保留三位小数）；
• 字母A-Z的分配方案，不同按键的字母组用单个空格分隔，字母按顺序排列。
  可能存在多个最优解，输出其中任意一个即可。

输入示例 1

2 
8 
8.167 1.492 2.782 4.253 12.702 2.228 2.015 6.094 6.966 0.153 0.772 4.025 2.406 
6.749 7.507 1.929 0.095 5.987 6.327 9.056 2.758 0.978 2.360 0.150 1.974 0.075 
9 
1.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 
10.0 10.0 10.0 10.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0

输出示例 1

1 1.647 AB CD EFG HIJK LM NOPQ RS TUVWXYZ  
2 1.570 A B CDEFG HIJKLM N OP QR STUV WXYZ  

来源

Greater New York Regional 2008