题解 | #购物单#

import sys

allwight, nums = map(int, input().strip().split(" "))
list1, list2, 编号 = [], [], 0


class 主件:
    def __init__(self, wight, value, 编号):
        self.value = value
        self.wight = wight
        self.编号 = 编号


class 附件:
    def __init__(self, 编号, wight, value):
        self.value = value
        self.wight = wight
        self.编号 = 编号


for i in range(1,nums+1):
    a = list(map(int, input().strip().split(" ")))
    if a[2] == 0:
        pey1 = 主件(a[0], a[1] * a[0], i)
        list1.append(pey1)
    else:
        fujian = 附件(a[2], a[0], a[1] * a[0])
        list2.append(fujian)
sumwight, sumvalue = [[]], [[]]
set1 = set([i.编号 for i in list2])
for i in list1:
    wightemp, valuetemp = [], []
    if i.编号 not in set1:
        wightemp.append(i.wight)
        valuetemp.append(i.value)
    else:
        listemp = [[j.wight, j.value] for j in list2 if j.编号 == i.编号]
        if len(listemp) == 1:
            wightemp.append(i.wight)
            valuetemp.append(i.value)
            wightemp.append(i.wight + listemp[0][0])
            valuetemp.append(i.value + listemp[0][1])
        else:
            wightemp.append(i.wight)
            valuetemp.append(i.value)
            wightemp.append(i.wight + listemp[0][0])
            valuetemp.append(i.value + listemp[0][1])
            wightemp.append(i.wight + listemp[1][0])
            valuetemp.append(i.value + listemp[1][1])
            wightemp.append(i.wight + listemp[0][0] +listemp[1][0])
            valuetemp.append(i.value + listemp[0][1]+ listemp[1][1])
    sumwight.append(wightemp)
    sumvalue.append(valuetemp)
nums = len(list1)
re = [[0]*(allwight//10+1) for _ in range(nums+1)]
for i in range(1,nums+1):
    for j in range(1,allwight//10+1):
        if j == 60 and i == 3:
            a=0
        if j*10 < min(sumwight[i]):
            re[i][j] = re[i-1][j]
        else:
            max1 = re[i-1][j]
            if len(sumwight[i]) == 1:
                resault1 = sumvalue[i][0] + re[i-1][j-sumwight[i][0]//10]
            else:
                resault1 = 0
                for k in range(len(sumwight[i])):
                    if sumwight[i][k] <= j*10:
                        max2 = sumvalue[i][k] + re[i-1][j-sumwight[i][k]//10]
                        resault1 = max(max2,resault1)
            re[i][j] = max(max1,resault1)
print(re[nums][allwight//10])