import java.io.*;
import java.util.Arrays;
import java.util.BitSet;
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] = Math.min(einleser.nextInt(), S / W[i]);
}
int[] dp = new int[S + 1];
dp[0] = 0;
int globalMax = 0;
for (int i = 0; i < N; i++) {
int amountUsed = K[i];
int k = 1;
while(amountUsed > 0) {
int use = Math.min(k, amountUsed);
int weight = W[i]*use;
int value = V[i]*use;
for (int j = S - weight; j >= 0; j--) {
int newIndex = j + weight;
int newValue = Math.max(dp[newIndex], dp[j] + value);
dp[newIndex] = newValue;
if (newValue > globalMax) {
globalMax = newValue;
}
}
amountUsed -= k;
k <<= 1;
}
}
einleser.write(String.valueOf(globalMax));
einleser.close();
}
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()));
}
}
}
