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))