import java.util.*;
import java.io.*;
public class knapsack {
public static void main(String[] args) throws IOException{
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(r.readLine());
int s = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken());
HashMap<Integer, ArrayList<int[]>> weight = new HashMap<>();
long[] dp = new long[s + 1]; //max value that can be obtained when the sum of weights is [s + 1] and the current weight your on is [n + 1]
// for (int i = 0; i <= s; i++) {
Arrays.fill(dp, -1);
// }
dp[0] = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(r.readLine());
int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());
if(!weight.containsKey(w)){
weight.put(w, new ArrayList<>());
}
weight.get(w).add(new int[]{v, k});
}
// int cur_Use = 1;
for (int e : weight.keySet()) {
ArrayList<int[]> arr = weight.get(e);
Collections.sort(arr, (a, b) -> -Integer.compare(a[0], b[0]));
// System.out.print(e + " ");
// for(int[] z : arr){
// System.out.print(Arrays.toString(z));
// }
for (int j = s; j >= 0; j--) {
// dp[j][cur_Use] = dp[j][cur_Use - 1];
int amt = 0;
int idx = 0;
int val = 0;
int used = 0;
while((amt + 1) * e <= j && idx < arr.size()){
amt++;
val += arr.get(idx)[0];
if(dp[j - (amt) * e] != -1){
dp[j] = Math.max(dp[j],
dp[j - amt * e] + val);
}
used++;
if(used == arr.get(idx)[1]){
used = 0;
idx++;
}
}
}
// cur_Use++;
}
long ans = 0;
for (int i = 0; i <= s; i++) {
ans = Math.max(ans, dp[i]);
}
pw.println(ans);
pw.close();
}
/*
public static void main(String[] args) throws IOException{
BufferedReader r = new BufferedReader(new FileReader("test.in"));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(r.readLine());
int s = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken());
int[][] options = new int[n][3];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(r.readLine());
int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());
options[i][0] = v;
options[i][1] = w;
options[i][2] = k;
}
int[] dp = new int[s + 1]; Arrays.fill(dp, -1); dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= s; j++) {
if(dp[j] != -1){
for (int j2 = 0; j2 < dp.length; j2++) {
}
}
}
System.out.println(i + " " + Arrays.toString(dp));
}
}
*/
}
