先贪心得出按Si * Li+1 < Si+1 * Li排序，再01背包

import java.io.*;
import java.util.*;

public class Main {

    private static class stone {
        int s;
        int e;
        int l;

        public stone(int s, int e, int l) {
            this.e = e;
            this.s = s;
            this.l = l;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
            int n = Integer.parseInt(br.readLine());
            stone[] stones = new stone[n + 1];
            int sum = 0;
            for (int t = 1; t <= n; t++) {
                String[] s1 = br.readLine().split(" ");
                int ss = Integer.parseInt(s1[0]);
                int ee = Integer.parseInt(s1[1]);
                int ll = Integer.parseInt(s1[2]);
                stones[t] = new stone(ss, ee, ll);
                sum += ss;
            }
            Arrays.sort(stones, 1, n+1, (v1, v2) -> v1.s * v2.l - v2.s * v1.l);
            //表示恰好为sum的最大值,需要初始化所有为负无穷，dp[0]为0
            int[] dp = new int[sum + 1];
            Arrays.fill(dp, -0x3f3f3f3f);
            dp[0] = 0;
            for (int j = 1; j <= n; j++) {
                int s = stones[j].s;
                int e = stones[j].e;
                int l = stones[j].l;
                for (int k = sum; k >= s; k--) {
                    dp[k] = Math.max(dp[k], dp[k - s] + e - (k - s) * l);
                }
            }
            int max = 0;
            for (int j = 1; j <= sum; j++) {
                max = Math.max(max, dp[j]);
            }
            System.out.println("Case" + " #" + i + ": " + max);
        }
    }
}