Optimizing Mobile Phone Text Entry

A standard mobile phone keypad assigns several letters to each numeric key in order. If a letter is the j-th letter assigned to its key, typing that letter requires pressing the key j times. For example, if A, B, and C are assigned to one key in that order, typing C requires three presses of that key.

You are given the usage frequency of each letter from A through Z and the number K of numeric keys that may be used. The alphabetical order must be preserved, so each key receives one contiguous block of letters. Every key must receive at least one letter and at most eight letters.

Assign the letters to the K keys so that the average number of key presses is minimized. The average is the sum, over all letters, of the number of presses for that letter multiplied by its frequency, divided by the sum of all frequencies.

The first line contains the number of test cases T.

Each test case consists of three lines. The first line contains the number of keys K. (4 <= K <= 26) The second line contains the usage frequencies of the 13 letters from A through M. The third line contains the usage frequencies of the 13 letters from N through Z.

For each test case, print one line. First print the minimum average number of key presses, rounded to three digits after the decimal point. Then print K strings separated by spaces, representing the assignment of A through Z. Each string is the contiguous block of letters assigned to one key.

If several assignments have the same minimum average, print the assignment whose K strings, joined by single spaces, form the lexicographically smallest string.