Monkey Hunter is an interplanetarily renowned online game. It provides a platform for all kinds of player, and the role they controlled can be stronger and stronger by making their effort on it. Players can get virtual props by completing some missions or defeating monkeys. The harder mission you complete, the rarer props you get.
They enjoy hunting in Monkey Hunter not only because of the game realistic senses, but the cooperation between players provides an almost real way to interact. Players have to talk to each other to make an efficient communication; otherwise they might have great difficulty to complete a team mission. A team can be divided into several small groups, and each group can contain any the number of roles.
In recently update, Monkey Hunter designed a new challenge “Paoxiao monkey” to be one of the most difficult challenges. Jelly’s team has spent a lot of time to challenge but they all failed. One of the failed reasons is the total power of defense in whole team is not high enough. When the two roles in the same group, there will be a bonus, additional increase or decrease in power of defense, due to the difference between the equipments, classes, races, and talents of two roles. The power of defense for whole team is the sum of all the characters’ power of defense and the sum of extra bonus.
Fortunately, Jelly has setup an additional plug-ins to compute the bonus between the two roles, but he still doesn’t know the possible maximum power of his team. You should find out the maximum power of defense in a certain grouping configuration.
The input consists of multiple test cases. The first line of each test case contains an integer N (0 < N ≤ 12), which is the number of characters. The next line contains N integers dps1, dps2, …, dpsN, where dpsi represents ith character’s power of defense. This line is followed by N lines, each of which contains N integers. The ith integer at jth line implies the bonus between ith role and jth role.
The last test case is followed by a line containing a single zero. There should be no more than 30 test cases.
For each test case, print the case number (starting with 1) followed by the maximum power of defense for whole team. Follow the format of the sample output.