import java.io.*;
import java.util.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;
/**
* @since 06.08.2025
*/
public final class knapsack {
public static void main(String[] args) {
Einleser einleser = new Einleser();
int S = einleser.nextInt();
int N = einleser.nextInt();
int[] V = new int[N];
int[] W = new int[N];
int[] K = new int[N];
for(int i = 0; i<N; i++) {
V[i] = einleser.nextInt();
W[i] = einleser.nextInt();
K[i] = einleser.nextInt();
}
int[] dp = new int[S + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
int globalMax = 0;
for (int i = 0; i < N; i++) {
int weight = W[i];
int value = V[i];
int copy = K[i];
for (int copies = 0; copies<copy; copies++) {
for (int j = S - weight; j >= 0; j--) {
if(dp[j] != -1) {
dp[j + weight] = Math.max(dp[j + weight], dp[j] + value);
if(dp[j + weight] > globalMax) {
globalMax = dp[j + weight];
}
}
}
}
}
System.out.println(globalMax);
}
private static final class Einleser extends PrintWriter {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public Einleser() {
this(System.in, System.out);
}
public Einleser(InputStream i, OutputStream o) {
super(o);
reader = new BufferedReader(new InputStreamReader(i));
}
public Einleser(String problemName) throws IOException {
super(problemName + ".out");
reader = new BufferedReader(new FileReader(problemName + ".in"));
}
public String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(reader.readLine());
return tokenizer.nextToken();
} catch (Exception e) {
}
return null;
}
public int nextInt() {
return Integer.parseInt(Objects.requireNonNull(next()));
}
public double nextDouble() {
return Double.parseDouble(Objects.requireNonNull(next()));
}
public long nextLong() {
return Long.parseLong(Objects.requireNonNull(next()));
}
}
}
