import java.util.*;
import java.io.*;
public class knapsack {
static BufferedReader in;
public static void main(String[] args) throws Exception {
in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = new StringTokenizer(in.readLine());
int s = Integer.parseInt(str.nextToken());
int n = Integer.parseInt(str.nextToken());
LinkedList<item> items = new LinkedList<>();
for(int i = 0; i < n; i ++) {
str = new StringTokenizer(in.readLine());
items.add(new item(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken())));
}
int[] dp = new int[s + 1];
dp[0] = 0;
int max = 0;
while(!items.isEmpty()) {
item next = items.poll();
for(int a = 0; a < next.copies; a ++) {
for(int b = s; b >= 0; b --) {
if(b + next.weight <= s) {
dp[b + next.weight] = Math.max(dp[b + next.weight], dp[b] + next.value);
max = Math.max(max, dp[b + next.weight]);
}
}
}
}
System.out.println(max);
}
static class item {
int value, weight, copies;
item(int value, int weight, int copies) {
this.value = value;
this.weight = weight;
this.copies = copies;
}
}
}
