import java.io.*;
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];
dp[0] = 0;
for (int i = 0; i < N; i++) {
int amountUsed = K[i];
int weight = W[i];
int value = V[i];
if(((long)weight*amountUsed)>=S) {
for (int j = 0; j <= S; j++) {
int newIndex = j + weight;
dp[newIndex] = Math.max(dp[newIndex], dp[j] + value);
}
} else {
int k = 1;
while(amountUsed > 0) {
int use = Math.min(k, amountUsed);
int currentWeight = weight*use;
int currentValue = V[i]*use;
for (int j = S - currentWeight; j >= 0; j--) {
int newIndex = j + currentWeight;
dp[newIndex] = Math.max(dp[newIndex], dp[j] + currentValue);
}
amountUsed -= k;
k <<= 1;
}
}
}
int globalMax = 0;
for(int v : dp) {
if(v > globalMax) {
globalMax = v;
}
}
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()));
}
}
}
