The Argentine football team coach, the great Diego Maradona, is going to try out a new formation this year. Formation describes how the players are positioned on the pitch.  Instead of the conventional 4-4-2 or 4-3-3, he has opted for 5-5. This means there are 5 attackers and 5 defenders.

You have been hired by Argentina Football Federation (AFF) to write a code that will help them figure out which players should take the attacking/defensive positions.

Maradona has given you a list containing the names of the 10 players who will take the field. The attacking ability and the defensive ability of each player are also given. Your job is to figure out which 5 players should take the attacking positions and which 5 should take the defensive positions.

The rules that need to be followed to make the decision are:

• The sum of the attacking abilities of the 5 attackers needs to be maximized
• If there is more than one combination, maximize the sum of the defending abilities of the 5 defenders
• If there is still more than one combination, pick the attackers that come lexicographically earliest.

Input

The first line of input contains an integer T(T<50) that indicates the number of test cases. Each case contains exactly 10 lines. The i^th line contains the name of the i^th player followed by the attacking and defending ability of that player respectively. The length of a player’s name is at most 20 and consists of lowercase letters only. The attacking/defending abilities are integers in the range [0, 99].

Output

The output of each case contains three lines. The first line is the case number starting from 1. The next line contains the name of the 5 attackers in the format (A₁, A₂, A₃, A₄, A₅) where A_i is the name of an attacker. The next line contains the name of the 5 defenders in the same format. The attackers and defenders names should be printed in lexicographically ascending order. Look at the sample for more details.

Problemsetter: Sohel Hafiz, Special Thanks: Shamim Hafiz, Jane Alam jan

先排序，之後就不用考慮名字的字典順序問題，按照字典順序窮舉就行了

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct p {
    string name;
    int a, b;
};
p P[10];
int at, def;
bool cmp(p a, p b) {
    int i;
    for(i = 0; i < a.name.length() && i < b.name.length(); i++)
        if(a.name[i] > b.name[i])
            return 0;
        else if(a.name[i] < b.name[i])
            return 1;
    return a.name.length() < b.name.length();
}
int A[10], B[10];
int aA[10], aB[10];
void dfs(int idx, int a, int d, int ta, int td) {
    if(idx == 10) {
        if(ta > at || (ta == at && td > def)) {
            at = ta, def = td;
            int i;
            for(i = 0; i < 5; i++)
                aA[i] = A[i], aB[i] = B[i];
        }
        return;
    }
    if(a != 5) {
        A[a] = idx;
        dfs(idx+1, a+1, d, ta+P[idx].a, td);
    }
    if(d != 5) {
        B[d] = idx;
        dfs(idx+1, a, d+1, ta, td+P[idx].b);
    }
}
int main() {
    int t, cases = 0, i;
    scanf("%d", &t);
    while(t--) {
        for(i = 0; i < 10; i++)
            cin >> P[i].name >> P[i].a >> P[i].b;
        sort(P, P+10, cmp);
        at = 0, def = 0;
        dfs(0, 0, 0, 0, 0);
        printf("Case %d:\n", ++cases);
        printf("(");
        for(i = 0; i < 5; i++) {
            if(i)   printf(", ");
            cout << P[aA[i]].name;
        }
        printf(")\n");
        printf("(");
        for(i = 0; i < 5; i++) {
            if(i)   printf(", ");
            cout << P[aB[i]].name;
        }
        printf(")\n");
    }
    return 0;
}