a = input()
a = list(a.split()) #输入的字符串以空格分开
budget = int(a[0]) #第一个字符代表预算值
want_num = int(a[1]) #第二个字符代表想要买的物品个数
main_goods = {}#表示主物品
remain_goods = {}#表示附属的物品
money_max = [0]*(budget + 1)#初始化一个长度为budget + 1的列表，初始化全为0
c = []
b = []

def calculate (key,value):
    price = []
    worth = []

    if key not in remain_goods:#为主物品
        price.append(main_goods[key][0]) #直接price为主物品价格,worth为价值乘积
        worth.append(main_goods[key][1])
    else:
        price.append(main_goods[key][0])#首先存主物品信息（只买主物品）
        worth.append(main_goods[key][1])
        if len(remain_goods[key]) == 1:#附属物品为1
            price.append(main_goods[key][0] + remain_goods[key][0][0])#买主物品和附属物品
            worth.append(main_goods[key][1] + remain_goods[key][0][1])
        else:#附属物品数量为2
            price.append(main_goods[key][0] + remain_goods[key][0][0])#买主物品和第一个附属物品
            worth.append(main_goods[key][1] + remain_goods[key][0][1])
            price.append(main_goods[key][0] + remain_goods[key][1][0])#买主物品和第二个附属物品
            worth.append(main_goods[key][1] + remain_goods[key][1][1])
            price.append(main_goods[key][0] + remain_goods[key][0][0]+ remain_goods[key][1][0])#买主物品和所有的附属物品
            worth.append(main_goods[key][1] + remain_goods[key][0][1]+ remain_goods[key][1][1]) #最后，price为[主物品价格，主物品+第一个附属物品总价格，主物品+第二个附属物品总价格， 主物品+两个附属物品总价格]代表对只买主物品，买主+一个附属（两种），买主+所有附属的不同尝试
    return price,worth

for i in range(want_num): 输入要买的物品价格，优先级，附属编号
    c = input()
    c = list(c.split())
    b.append([int(c[0]),int(c[1]),int(c[2])])#分开后放入b中
    
for i in range(want_num):
    if(b[i][2] == 0):#为主物品
        main_goods[i+1] = [b[i][0],b[i][0]*b[i][1]] #存为 编号：[价格，价格*优先级]
    else:#为附属物品
        if(b[i][2] not in remain_goods):#附属物品字典里面还没有存某主物品的附属信息
            remain_goods[b[i][2]] = []#将此字典的value设定为二维列表，因为每个主物品最多有2个附属
            remain_goods[b[i][2]].append([b[i][0],b[i][0]*b[i][1]])#添加附属信息
        else:#已经有了对应主物品的附属信息
            remain_goods[b[i][2]].append([b[i][0],b[i][0]*b[i][1]])#直接在对应主物品的附属信息二维列表添加一行即可
            
for key,value in main_goods.items():#key为主物品的编号，value为价格和价值乘积
    price,worth = calculate(key, value)price为主物品价格，worth为价值乘积
    for i in range(budget,-1,-10):#以i = budget为初始值开始循环，每次i = i - 10
        for k in range(len(price)):#price有几个值，（主物品为1，附属物品为多个）
            if i - price[k] >= 0:#当前i值买的起
                money_max[i] = max(money_max[i],money_max[i - price[k]] + worth[k])#计算当前i值能买的起的最大价值乘积
print(money_max[budget])#输出budget的最大价值乘积

ps:确定这个只是中等难度吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？