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());
int[][] info = new int[n][3];
long ans = -1;
long[] weight = new long[s + 1];
Arrays.fill(weight, Integer.MIN_VALUE);
weight[0] = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(r.readLine());
info[i][0] = Integer.parseInt(st.nextToken());
info[i][1] = Integer.parseInt(st.nextToken());
info[i][2] = Math.min(s/info[i][1], Integer.parseInt(st.nextToken()));
}
for (int[] e : info) {
for (int i = s; i >= e[1]; i--) {
for (int j = e[2]; j > 0; j--) {
if(i - j * e[1] < 0){
continue;
}
weight[i] = Math.max(weight[i], weight[i - j * e[1]] + e[0] * j);
}
}
}
for(long e : weight){
ans = Math.max(e, ans);
}
pw.close();
}
}
