题解 | #购物单#

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {
    public static void main(String[]args) throws IOException {

        Scanner in = new Scanner(System.in);

        int money = in.nextInt();
        int count = in.nextInt();

        int[] v = new int[count + 1];
        int[] p = new int[count + 1];
        int[] q = new int[count + 1];
        int[] f1 = new int[count + 1];
        int[] f2 = new int[count + 1];

        boolean flag = true;
        int dw = 100;

        // 数据录入
        if (money == 0 || count == 0) {
            System.out.println(0);
            return;
        }

        for (int i = 1 ; i < count + 1; i++) {

            v[i] = in.nextInt();
            if (flag && v[i] % dw != 0) {
                dw = 10;
                flag = false;
                for (int m = 1 ; m < i ; m++) {
                    p[m] *= 10;
                    v[m] *= 10;

                }

            }
            v[i] = v[i] / dw;
            p[i] = in.nextInt() * v[i];
            q[i] = in.nextInt();

            if (q[i] > 0) {

                if (f1[q[i]] == 0) {
                    f1[q[i]] = i;

                } else {
                    f2[q[i]] = i;
                }

            }

        }

        // 处理数据
        money /= dw;
        int[][] dp = new int[count + 1][money + 1];

        for (int i = 1 ; i < count + 1 ; i++) {

            int p1 = 0, p2 = 0, p3 = 0;
            int v1 = -1, v2 = -1, v3 = -1;

            if (f1[i] != 0) {
                v1 = v[i] + v[f1[i]];
                p1 = p[i] + p[f1[i]];

            }


            if (f2[i] != 0) {
                v2 = v[i] + v[f2[i]];
                p2 = p[i] + p[f2[i]];

            }


            if (f1[i] != 0 && f2[i] != 0) {
                v3 = v1 + v2 - v[i];
                p3 = p1 + p2 - p[i];

            }


            for (int j = 1 ; j < money + 1 ; j ++) {

                dp[i][j] = dp[i - 1][j];

                if (q[i] == 0) {

                    if (j >= v[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + p[i]);

                    }
                    if (v1 != -1 && j >= v1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + p1);

                    }

                    if (v2 != -1 && j >= v2) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + p2);

                    }

                    if (v3 != -1 && j >= v3) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + p3);

                    }
 
                }

            }




        }
   


        System.out.println(dp[count][money] * dw);




    }
}