max_capacity, items_cnt = map(int, input().split())
prev_state = [0] * (max_capacity + 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):
if cur_capacity > 0:
new_state[cur_capacity] = max(new_state[cur_capacity], new_state[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)
prev_state = new_state
print(prev_state[-1])
