"""
Task 2: Knapsack
There is a housewife who recently won a prize to “shop for free as long as your shopping basket
is not full” in a department store.
This housewife is given a shopping basket that can carry a maximal weight of S kilograms.
There are N item types in the department store and the i-th item is worth Vi SGD, weighs
Wi kilograms, and there are Ki copies (of exactly same value and weight) of such item i.
For example, there are N = 3 item types: meat, milk, and bread; of which there are: 1 pack of
meat, 3 bottles of milk, and 4 loaves of bread (see the last sample test case).
What items should the housewife take to maximize the total value of the items in her shop-
ping basket?
Input format
Your program must read from standard input.
The first line of input contains two positive integers, S and N .
The next N lines of input will each contain three integers, where the i-th line contains Vi, Wi
and Ki, the value in SGD, weight in kilograms and number of the i-th item respectively.
Output format
Your program must print to standard output.
Your program should print one integer, representing the maximum total value in SGD of the
items that this housewife can take while ensuring the total weight does not exceed S kilograms.
Sample Testcase 1
This testcase is valid for subtasks 2-5.
Input Output
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
15
Explanation
The housewife can take one of items 2, 3, 4, 5 giving a total weight of 1 + 4 + 1 + 2 = 8 and a
total value of 2 + 10 + 1 + 2 = 15.
Sample Testcase 2
This testcase is valid for subtasks 3-5.
Input Output
20 3
5000 15 1
100 1 3
50 1 4
5400
Explanation
The housewife take one of item 1, three of item 2 and two of item 3 for a total weight of
15 × 1 + 1 × 3 + 1 × 2 = 20 and a total value of 5000 × 1 + 100 × 3 + 50 × 2 = 5400.
NOI 2018 National Olympiad in Informatics—Singapore 6
"""
import sys
import math
from functools import lru_cache
# sys.stdin = open("feast.in", "r")
# sys.stdout = open("feast.out", "w")
# V W K
def solve():
MAX_W, n = list(map(int, input().split()))
Vs, Ws, Ks = [], [], []
for i in range(n):
V, W, K = list(map(int, input().split()))
Vs.append(V)
Ws.append(W)
Ks.append(K)
@lru_cache(None)
def dp(w, i, k):
"""
given current weight w, select item i, have k times left
"""
best = 0 #float('-inf')
# get current item i, keep getting i
if k>0 and w-Ws[i] >= 0: # if item i on stock, weight fit basket
best = max(best, dp(w-Ws[i], i, k-1) + Vs[i])
if i+1 < n: # if not the last item in list
# don't get item i, move to item i+1
best = max(
best,
dp(w, i+1, Ks[i+1]),
)
return best
return dp(MAX_W, 0, Ks[0])
print(solve())
