import java.io.*;
import java.util.StringTokenizer;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int s = Integer.parseInt(tokenizer.nextToken());
int n = Integer.parseInt(tokenizer.nextToken());
item[] items = new item[n+1];
int[][] dp = new int[n+1][s+1];
dp[0][0] = 1;
for (int i = 1; i < n+1; i++) {
tokenizer = new StringTokenizer(in.readLine());
items[i] = new item(Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()));
}
// for (int i = 0; i < n; i++) {
// int v = items[i+1].v;
// int w = items[i+1].w;
// int k = items[i+1].k;
// for (int j = 0; j < s+1; j++) {
// if (dp[i][j] >= 0) {
// for (int count = 0; count <= k; count++) {
// if (j + w * count <= s) {
// dp[i+1][j+w*count] = Math.max(dp[i+1][j+w*count], dp[i][j] + v*count);
// }
// else {
// break;
// }
// }
// }
// }
// }
int ans = 0;
for (int i = 1; i < n+1; i++) {
int v = items[i].v;
int w = items[i].w;
int k = items[i].k;
for (int j = 0; j < s+1; j++) {
for (int count = 0; count <= k; count++) {
if (j - w * count >= 0) {
if (dp[i-1][j - w * count] >= 1) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w*count] + v * count);
ans = Math.max(ans, dp[i][j]);
}
}
else {
break;
}
}
}
}
System.out.println(ans-1);
}
static class item {
int v, w, k;
item(int v, int w, int k) {
this.v = v;
this.w = w;
this.k = k;
}
}
}
