题解 | #购物单#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner fzhinput = new Scanner(System.in);
        int money = fzhinput.nextInt();
        int num = fzhinput.nextInt();
        int price[] = new int[num + 1];
        int important[] = new int[num + 1];
        int morq[] = new int[num + 1];
        int[][] attach = new int[num + 1][2];
        int i;
        int my[] = new int[money + 1];
        fzhinput.nextLine();
        for (i = 1; i <= num; i++) {
            price[i] = fzhinput.nextInt();
            important[i] = fzhinput.nextInt();
            morq[i] = fzhinput.nextInt();
            if (morq[i] > 0) {
                // 如果是附件，找到对应主件
                if (attach[morq[i]][0] == 0) {
                    attach[morq[i]][0] = i; // 第一个附件
                } else {
                    attach[morq[i]][1] = i; // 第二个附件
                }
            }
        }

       for (i = 1; i <= num; i++) {
            if (morq[i] == 0) { // 处理主件
                // 逆序遍历，保证每个物品只用一次
                for (int j = money; j >= price[i]; j--) {
                    // 仅购买主件
                    my[j] = Math.max(my[j], my[j - price[i]] + price[i] * important[i]);

                    // 买主件 + 第一个附件
                    if (attach[i][0] > 0 && j >= price[i] + price[attach[i][0]]) {
                        my[j] = Math.max(my[j], my[j - price[i] - price[attach[i][0]]] + price[i] * important[i] + price[attach[i][0]] * important[attach[i][0]]);
                    }

                    // 买主件 + 第二个附件
                    if (attach[i][1] > 0 && j >= price[i] + price[attach[i][1]]) {
                        my[j] = Math.max(my[j], my[j - price[i] - price[attach[i][1]]] + price[i] * important[i] + price[attach[i][1]] * important[attach[i][1]]);
                    }

                    // 买主件 + 两个附件
                    if (attach[i][0] > 0 && attach[i][1] > 0 && j >= price[i] + price[attach[i][0]] + price[attach[i][1]]) {
                        my[j] = Math.max(my[j], my[j - price[i] - price[attach[i][0]] - price[attach[i][1]]] + price[i] * important[i] + price[attach[i][0]] * important[attach[i][0]] + price[attach[i][1]] * important[attach[i][1]]);
                    }
                }
            }
        }
        System.out.println(my[money]);

    }
}