#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<cmath>
using namespace std;
const int N = 10003, inf = 0x3f3f3f3f;
typedef pair<int, int> PIR;
typedef long long ll;
struct Stone
{
int s, e, l;
bool operator <(const Stone S) const
{
return s * S.l < S.s* l;
}
}stone[N];
int f[N];//f[i][j]:从前i个物品中选，时间恰好是j的集合
int main()
{
int T;
cin >> T;
for (int kase = 1; kase <= T; kase++)
{
int n, m = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int s, e, l;
cin >> s >> e >> l;
stone[i] = { s,e,l };
m += s;
}
sort(stone, stone + n);
/*整个解空间具有不确定性，即不能确定先选哪个再选哪个，对于第i个物品，如果先选
第i个则有e[i]+e[i+1]-s[i]*l[i+1];先选第i+1个，则有e[i]+e[i+1]-s[i+1]*l[i]
如果s[i]*l[i+1]<s[i+1]*l[i]则说明最优解一定是先选第i个，反之亦然；所以先对
能量石排序，确定选择顺序，缩小解空间的规模
*/
memset(f, -0x3f3f3f3f, sizeof f);
f[0] = 0;
for (int i = 0; i < n; i++)
{
int s = stone[i].s, e = stone[i].e, l = stone[i].l;
for (int j = m; j >= stone[i].s; j--)
f[j] = max(f[j], f[j - s] + e - (j - s) * l);
}
int res = 0;
for (int i = 0; i <= m; i++)
res = max(res, f[i]);
printf("Case #%d: %d\n", kase, res);
}
return 0;
}
