//package ojuz;
import java.io.*;
import java.util.*;
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]);
int[] dp = new int[s + 1];
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]);
k = Math.min(k, s / w);
int log = 31 - Integer.numberOfLeadingZeros(k);
for (int j = 0; j < log; j++) {
for (int l = s; l >= w; l--) {
dp[l] = Math.max(dp[l], dp[l - w] + v);
}
w <<= 1;
v <<= 1;
}
int mult = k - (1 << log) + 1;
w >>= log;
v >>= log;
w *= mult;
v *= mult;
for (int j = s; j >= w; j--) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
System.out.println(dp[s]);
}
}
