def knapsack():
# Read input
limit, type_num = map(int, input().split())
# Create a list to store items grouped by their weights
by_weight = []
# Populate the list with items
for _ in range(type_num):
value, weight, amount = map(int, input().split())
if weight <= limit and amount > 0:
by_weight.append((weight, value, amount))
# Sort items in ascending order by weight
by_weight.sort()
# Initialize a 2D list to store the best values for different weights and item types
best = [[0] * (limit + 1) for _ in range(len(by_weight) + 1)]
# Iterate through each item type
for i, (w, v, a) in enumerate(by_weight, start=1):
for j in range(limit + 1):
best[i][j] = best[i - 1][j]
for k in range(1, a + 1):
if k * w <= j:
best[i][j] = max(best[i][j], best[i - 1][j - k * w] + k * v)
# Find the maximum value achievable and print it
most_value = max(best[len(by_weight)][i] for i in range(limit + 1))
print(most_value)
if __name__ == "__main__":
knapsack()
