# N 总钱数
# m 希望购买的物品个数
# 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
# （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。
# 如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
# 输出描述：
# 输出一个正整数，为张强可以获得的最大的满意度。
# 800 2 0
# 400 5 1
# 300 5 1
# 400 3 0
# 500 2 0
# 将此问题等价为背包问题，购买分为：1、购买主件；2、购买主件 + 附件1；3、购买主件 + 附件2；4、购买主件 + 附件1 + 附件2
# 设 w[i][k] 表示，第i件物品的第k种购买情况的价格，k 取值 0,1,2,3 对应上面四种情况
# 设 v[i][k] 表示，第i件物品的第k种购买情况的满意度，k 取值同上
# 获取到输入的主件个数作为背包问题输入的物品个数，总钱数为背包容量
while True:
try:
n, m = map(int, input().split())
primary = {} # 存储主件信息
annes = {} # 存储附件信息
for i in range(1,m + 1):
x, y, z = map(int, input().split())
if z == 0: # 主件标识，识别为主件
primary[i] = [x, y]
else:
if z in annes: # 第二个附件，加入
annes[z].append([x, y]) # 第二个附件，添加到已存在的附件列表里边即可
else:
annes[z] = [[x, y]] # 第一个附件，附初始值 ；一个主件可能有1个或两个附件，故设计为二维数组形式
# 获取主件的个数，作为物品个数
m = len(primary)
# 涉及状态转换数组 dp[][] ; dp[i][j] 表示在背包容量为j时，第i个物品放入背包后，背包存储的物品最大价值
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 进行向背包问题的转换,附件问题处理： w[i][k],v[i][k]
w, v = [[]] , [[]] # 存储等价抓换后的每个物品的 w[][]和 v[][]
for key in primary: # 遍历存储主件的字典
w_temp, v_temp = [], []
w_temp.append(primary[key][0]) # 1.主件key的重量
v_temp.append(primary[key][0] * primary[key][1]) # 主件key的价值
if key in annes: # 该主键存在附件
w_temp.append(w_temp[0] + annes[key][0][0]) # 2.主件 + 附件1 的重量
v_temp.append(v_temp[0] + annes[key][0][0] * annes[key][0][1]) # 主件 + 附件1的价值
if len(annes[key]) > 1: # 该主键存在两个附件
w_temp.append(w_temp[0] + annes[key][1][0]) # 主件 + 附件2 的重量
v_temp.append(v_temp[0] + annes[key][1][0] * annes[key][1][1]) # 主件 + 附件2 的价值
w_temp.append(w_temp[0] + annes[key][0][0] + annes[key][1][0]) # 主件 + 附件1 + 附件2的重量
v_temp.append(v_temp[0] + annes[key][0][0] * annes[key][0][1] + annes[key][1][0] * annes[key][1][1])
w.append(w_temp)
v.append(v_temp)
# 进行典型背包问题的迭代
for i in range(1, m + 1): # 按物品个数进行循环
for j in range(10, n + 1,10): # 背包容量是10的整数倍递增的
max_i = dp[i - 1][j]
for k in range(len(w[i])):
if j - w[i][k] >= 0:
max_i = max(max_i, dp[i-1][j - w[i][k]] + v[i][k])
dp[i][j] = max_i
print(dp[m][n])
except:
break
