//package ojuz;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] first = reader.readLine().split(" ");
int s = Integer.parseInt(first[0]), n = Integer.parseInt(first[1]);
List<int[]> items = new ArrayList<>();
for (int i = 0; i < n; i++) {
String[] arr = reader.readLine().split(" ");
int v = Integer.parseInt(arr[0]), w = Integer.parseInt(arr[1]), k = Integer.parseInt(arr[2]);
if (k == 1) {
items.add(new int[] {v, w});
continue;
}
int log = 31 - Integer.numberOfLeadingZeros(k);
for (int j = 0; j < log; j++) {
// System.out.println(log);
items.add(new int[] {v << j, w << j});
}
int mult = k - (1 << log) + 1;
// System.out.println("mult: " + mult);
items.add(new int[] {v * mult, w * mult});
}
// System.out.println(items.stream().map(Arrays::toString).collect(Collectors.toList()));
long[] dp = new long[s + 1];
for (int[] item : items) {
for (int i = s; i >= item[1]; i--) {
dp[i] = Math.max(dp[i], dp[i - item[1]] + item[0]);
}
}
System.out.println(dp[s]);
}
}
