import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer initial = new StringTokenizer(read.readLine());
int limit = Integer.parseInt(initial.nextToken());
int typeNum = Integer.parseInt(initial.nextToken());
HashMap<Integer, ArrayList<int[]>> byWeight = new HashMap<>();
for (int t = 0; t < typeNum; t++) {
StringTokenizer item = new StringTokenizer(read.readLine());
int value = Integer.parseInt(item.nextToken());
int weight = Integer.parseInt(item.nextToken());
int amt = Integer.parseInt(item.nextToken());
if (weight <= limit && 0 <= amt) {
if (!byWeight.containsKey(weight)) {
byWeight.put(weight, new ArrayList<>());
}
byWeight.get(weight).add(new int[] {value, amt});
}
}
long[][] best = new long[byWeight.size() + 1][limit + 1];
for (long[] row : best) {
Arrays.fill(row, Integer.MIN_VALUE);
}
best[0][0] = 0;
int at = 1;
for (var pair : byWeight.entrySet()) {
int w = pair.getKey();
ArrayList<int[]> items = pair.getValue();
items.sort(Comparator.comparingInt(i -> -i[0]));
for (int i = 0; i <= limit; i++) {
best[at][i] = best[at - 1][i];
int copies = 0;
int typeAt = 0;
int curr_used = 0;
long profit = 0;
while ((copies + 1) * w <= i && typeAt < items.size()) {
copies++;
profit += items.get(typeAt)[0];
if (best[at - 1][i - copies * w] != Integer.MIN_VALUE) {
best[at][i] = Math.max(
best[at][i],
best[at - 1][i - copies * w] + profit
);
}
curr_used++;
if (curr_used == items.get(typeAt)[1]) {
curr_used = 0;
typeAt++;
}
}
}
at++;
}
long mostValue = 0;
for (int i = 0; i <= limit; i++) {
mostValue = Math.max(mostValue, best[byWeight.size()][i]);
}
System.out.println(mostValue);
}
}
