max_capacity, items_cnt = map(int, input().split())
prev_state = [0] * (max_capacity + 1)
# 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())
new_state = prev_state.copy()
for cur_capacity in range(max_capacity + 1):
# dp[item_i + 1][cur_capacity] = dp[item_i][cur_capacity]
if cur_capacity > 0:
new_state[cur_capacity] = max(new_state[cur_capacity], new_state[cur_capacity - 1])
# 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
new_state[cur_capacity] = max(new_state[cur_capacity], prev_state[cur_capacity - cur_quantity * weight] + cur_quantity * value)
# dp[item_i + 1][cur_capacity] = max(dp[item_i + 1][cur_capacity], dp[item_i][cur_capacity - cur_quantity * weight] + cur_quantity * value)
prev_state = new_state
# print(dp[-1][-1])
print(prev_state[-1])
