max_capacity, items_cnt = map(int, input().split())
dp = [[0] * (max_capacity + 1) for _ in range(items_cnt + 1)]
for item_i in range(items_cnt):
value, weight, quantity = map(int, input().split())
for cur_capacity in range(max_capacity + 1):
dp[item_i + 1][cur_capacity] = dp[item_i][cur_capacity]
if cur_capacity > 0:
dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - 1])
for cur_quantity in range(1, quantity + 1):
if cur_quantity * weight > cur_capacity:
break
dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - cur_quantity * weight] + cur_quantity * value)
print(dp[-1][-1])
# print(*dp, sep='\n')
"""
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
"""
"""
20 3
5000 15 1
100 1 3
50 1 4
"""
