#dp[i][j] --- i represents using the first i items where items w same weight are grouped and j is the total weight
import math
s, n = map(int, input().split())
item_dict = {}
for x in range(n):
v, w, k = map(int, input().split())
if w in item_dict:
for y in range(k):
item_dict[w].append(v)
else:
item_dict[w] = [v for y in range(k)]
for key in item_dict.keys():
item_dict[key].sort(reverse=True)
items = sorted(item_dict.keys())
dp = [[0 for j in range(s+1)] for i in range(len(items)+1)]
for j in range(s+1):
for i in range(0, len(items)):
dp[i+1][j] = dp[i][j]
for k in range(len(item_dict[items[i]])):
if j-items[i]*(k+1) >= 0:
dp[i+1][j] = max(dp[i+1][j], dp[i][j-items[i]*(k+1)] + sum(item_dict[items[i]][:k+1]))
#dp[i+1][j] = max(dp[i+1][j], sum(item_dict[items[i]][:min(len(item_dict[items[i]]), math.ceil(s/items[i]))]))
print(dp[-1][-1])
