import java.util.*;
public class knapsack {
static int n, s;
static int[][] item; // {value, weight, count}
static int[][] dp; // memo idx×currWt, -1 = unvisited
static int solve(int idx, int currWt) {
if (currWt > s) return Integer.MIN_VALUE; // overweight
if (idx == n) return 0; // no more items
if (dp[idx][currWt] != -1) return dp[idx][currWt];
int best = 0;
int v = item[idx][0];
int w = item[idx][1];
int c = item[idx][2];
// try taking t copies, 0 … c
for (int t = 0; t <= c && currWt + t * w <= s; t++) {
int candidate = t * v + solve(idx + 1, currWt + t * w);
best = Math.max(best, candidate);
}
return dp[idx][currWt] = best;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s = sc.nextInt(); // capacity
n = sc.nextInt(); // item types
item = new int[n][3];
for (int i = 0; i < n; i++) {
item[i][0] = sc.nextInt(); // value
item[i][1] = sc.nextInt(); // weight
item[i][2] = sc.nextInt(); // count
}
dp = new int[n][s + 1];
for (int[] row : dp) Arrays.fill(row, -1);
System.out.println(solve(0, 0));
}
}
