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][n + 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[i], Long.MIN_VALUE);
}
dp[0][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][cur_Use - 1] != Long.MIN_VALUE){
// System.out.println(cur_Use - 1 + " " + (j - (amt + 1) * e));
dp[j][cur_Use] = Math.max(dp[j][cur_Use],
dp[j - amt * e][cur_Use - 1] + val);
}
used++;
if(used == arr.get(idx)[1]){
used = 0;
idx++;
}
}
}
cur_Use++;
// System.out.println();
}
long ans = 0;
for (int i = 0; i <= s; i++) {
ans = Math.max(ans, dp[i][n - 1]);
}
// for(long[] e : dp){
// System.out.println(Arrays.toString(e));
// }
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));
}
}
*/
}
