Interpersonal dislikes P98089

Given n people and the grade of dislike between them, choose how to make them sit at a long table, in such a way that the sum of the interpersonal dislikes of the neighbor persons is minimum, with one restriction: the leftmost person must be the first person given.

Input

Input consists of several cases, each with n, followed by n different names, followed by an n × n matrix of natural numbers between 0 and 10⁶, where the position (i, j) has the dislike between people i and j. The matrix is symmetric, with zeroes at the diagonal. You can assume 1 ≤ n ≤ 12.

Output

For every case, print the minimum sum of dislikes, followed by the optimum placement of people at the table. The test cases are such that there is always a unique solution.