# s,n=map(int,input().split())
# v,w,k=[0]*n,[0]*n,[0]*n
# for i in range(n):
# v[i],w[i],k[i]=map(int,input().split())
# dp=[-float("inf")]*(s+1)
# dp[0]=0
# for i in range(n):
import sys
def knapsack(limit, type_num, items):
by_weight = {}
for value, weight, amt in items:
if weight <= limit and amt > 0:
if weight not in by_weight:
by_weight[weight] = []
by_weight[weight].append((value, amt))
best = [[-float('inf')] * (limit + 1) for _ in range(len(by_weight) + 1)]
best[0][0] = 0
at = 1
for w, item_list in sorted(by_weight.items()):
item_list.sort(reverse=True, key=lambda x: x[0]) # Sort items by value in descending order
for i in range(limit + 1):
best[at][i] = best[at - 1][i]
copies, type_at, curr_used, profit = 0, 0, 0, 0
while (copies + 1) * w <= i and type_at < len(item_list):
copies += 1
profit += item_list[type_at][0]
if best[at - 1][i - copies * w] != -float('inf'):
best[at][i] = max(best[at][i], best[at - 1][i - copies * w] + profit)
curr_used += 1
if curr_used == item_list[type_at][1]:
curr_used = 0
type_at += 1
at += 1
return max(best[-1])
if __name__ == "__main__":
limit, type_num = map(int, sys.stdin.readline().split())
items = [tuple(map(int, sys.stdin.readline().split())) for _ in range(type_num)]
print(knapsack(limit, type_num, items))
