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] = einleser.nextInt();
}
BitSet setBits = new BitSet(S + 1);
int[] dp = new int[S + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
setBits.set(0);
int globalMax = 0;
for (int i = 0; i < N; i++) {
int weight = W[i];
int value = V[i];
int copy = Math.min(K[i], S/weight);
for (int copies = 0; copies<copy; copies++) {
for (int j = setBits.previousSetBit(S - weight); j >= 0; j = setBits.previousSetBit(j - 1)) {
if(dp[j] != -1) {
int newIndex = j + weight;
int newValue = Math.max(dp[newIndex], dp[j] + value);
dp[newIndex] = newValue;
setBits.set(newIndex);
if(newValue > globalMax) {
globalMax = newValue;
}
}
}
}
}
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()));
}
}
}
