import java.io.*;
import java.util.*;
public class knapsack {
static int maxW, n;
static Item[] arr;
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader file = new BufferedReader(new FileReader("file.in"));
StringTokenizer st = new StringTokenizer(file.readLine());
maxW = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
arr = new Item[n];
for (int i=0; i<n; i++){
st = new StringTokenizer(file.readLine());
arr[i] = new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
long[][] dp = new long[maxW+1][n+1];
for (int i=1; i<=maxW; i++){
for (int j=1; j<=n; j++){
for (int k=1; k <= arr[j-1].k; k++){
if (i >= (long)arr[j-1].weight*k){
dp[i][j] = Math.max(dp[i][j], dp[i-arr[j-1].weight*k][j-1] + (long)arr[j-1].val*k);
}
}
}
}
System.out.println(dp[maxW][n]);
}
static class Item{
int val, weight, k;
public Item(int weight, int val, int k){
this.val = val;
this.weight = weight;
this.k = k;
}
}
}
