from collections import defaultdict money,amount = map(int,input().split()) main_items = [] atta_items = defaultdict(list) dp = [0]*(money+1) for i in range(amount): v,imp,m = map(int,input().split()) if m == 0: main_items.append([v,imp,i+1]) else: atta_items[m].append([v,imp]) for main_item in main_items: v0,w0=main_item[0],main_item[1]*main_item[0] attach = atta_items[main_item[2]] combos = [(v0,w0)] if len(attach)==1: v1,w1 =attach[0][0],attach[0][0]*attach[0][1] combos.append((v0+v1,w0+w1)) if len(attach)==2: v1,w1 =attach[0][0],attach[0][0]*attach[0][1] v2,w2 =attach[1][0],attach[1][0]*attach[1][1] combos.append((v0+v1,w0+w1)) combos.append((v0+v2,w0+w2)) combos.append((v0+v1+v2,w0+w1+w2)) dp_old = dp[:] for cost,weight in combos: for i in range(money,cost-1,-1): dp[i]=max(dp[i],dp_old[i-cost]+weight) print(max(dp))