import math
from functools import reduce
# Used by bounded knapsack
def zero_one_knapsack(weights, values, weight_limit: int) -> int:
w_gcd = reduce(math.gcd, [*weights, weight_limit])
weights = [w // w_gcd for w in weights]
weight_limit //= w_gcd
dp = [0] * (weight_limit + 1)
for item_i in range(len(weights)):
new_dp = dp.copy()
for w in range(weights[item_i], weight_limit + 1):
new_dp[w] = max(dp[w], dp[w - weights[item_i]] + values[item_i])
dp = new_dp
return dp[weight_limit]
def bounded_knapsack(weights, values, quantities, weight_limit: int) -> int:
adjusted_items = []
for w, v, q in zip(weights, values, quantities):
for pow_two in range(q.bit_length()):
adjusted_items.append((w * (1 << pow_two), v * (1 << pow_two)))
return zero_one_knapsack([item[0] for item in adjusted_items], [item[1] for item in adjusted_items], weight_limit)
if __name__ == '__main__':
weight_limit, items_cnt = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(items_cnt)]
vs = [i[0] for i in items]
ws = [i[1] for i in items]
qs = [i[2] for i in items]
print(bounded_knapsack(ws, vs, qs, weight_limit))
