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();
Queue<Integer> processNext = new LinkedList<>();
for(int b = s; b >= 0; b --) {
if(b + next.weight <= s) {
if(dp[b + next.weight] < dp[b] + next.value) {
dp[b + next.weight] = dp[b] + next.value;
processNext.add(b + next.weight);
}
max = Math.max(max, dp[b + next.weight]);
}
}
for(int a = 1; a < next.copies; a ++) {
int times = processNext.size();
if(times == 0)
break;
for(int b = 0; b < times; b ++) {
int ind = processNext.poll();
if(ind + next.weight <= s && dp[ind + next.weight] < dp[ind] + next.value) {
dp[ind + next.weight] = dp[ind] + next.value;
processNext.add(ind + next.weight);
max = Math.max(max, dp[ind + 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;
}
}
}
