#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N = 110,M=10010;
int f[M], t, n; 

struct nb{
    int s, e, l;
}g[N];

bool cmp(struct nb a,struct nb b)
{
    return a.s * b.l < a.l * b.s;
}

int main()
{
    cin >> t;
    for(int k = 1; k <= t; k ++)
    {  
        cin >> n;
        int m = 0, res = 0;
        for(int i = 1; i <= n; i ++) cin >> g[i].s >> g[i].e >> g[i].l;
        for(int i = 1; i <= n; i ++) m += g[i].s;
        sort(g + 1, g + 1 + n, cmp);


        memset(f, -0x3f, sizeof(f));
        f[0] = 0;

        for(int i = 1; i <= n; i ++)
        {
            for(int j = m; j >= g[i].s; j --)
            {
                f[j] = max(f[j], f[j - g[i].s] - (j - g[i].s) * g[i].l + g[i].e);
                res = max(res, f[j]);
            }
        }

        printf("Case #%d: %d\n", k, res);

    }

    return 0;   
}