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[]>> weights = new HashMap<>(); //weight with respect to [price, amount]
for (int i = 0; i < n; i++) {
st = new StringTokenizer(r.readLine());
int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken());
if(!weights.containsKey(b)){
weights.put(b, new ArrayList<>());
}
weights.get(b).add(new int[]{a, c});
}
long[][] ans = new long[weights.size() + 1][s + 1];
for (int i = 0; i < ans.length; i++) {
Arrays.fill(ans[i], Long.MIN_VALUE);
}
ans[0][0] = 0;
long max = 0;
int z = 1;
for(int e : weights.keySet()){
ArrayList<int[]> possible = weights.get(e);
Collections.sort(possible, (a, b) -> -Integer.compare(a[0], b[0]));
for (int i = 0; i <= s; i++) {
ans[z][i] = ans[z - 1][i];
int cur = 0;
int at = 0;
int total = 0;
long profit = 0;
while(i - (total + 1) * e >= 0 && cur < possible.size()){
total ++;
profit += possible.get(cur)[0];
if(ans[z - 1][i - total * e] != Long.MIN_VALUE){
ans[z][i] = Math.max(ans[z][i], ans[z - 1][i - total * e] + profit);
max = Math.max(ans[z][i], max);
}
at ++;
if(at == possible.get(cur)[1]){
at = 0;
cur ++;
}
}
}
z++;
}
pw.println(max);
pw.close();
}
}
