import java.io.*;
import java.util.*;
public class knapsack {
static int maxW, n;
static TreeMap<Integer, ArrayList<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 TreeMap<>();
for (int i=0; i<n; i++){
st = new StringTokenizer(file.readLine());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
if (!arr.containsKey(w)){
arr.put(w, new ArrayList<>());
}
arr.get(w).add(new Item(v, w, k));
}
long[] dp = new long[maxW+1];
long[] pdp = new long[maxW+1];
for (int currW : arr.keySet()){
ArrayList<Item> curr = arr.get(currW);
Collections.sort(curr, (a, b) -> b.val-a.val);
int iters = maxW/currW;
for (int j=0; j<iters && j < curr.size(); j++){
Item currItem = curr.get(j);
for (int i=1; i<=maxW; i++){
dp[i] = pdp[i];
for (int k=1; currItem.weight*k<=i && k <= currItem.k; k++){
if (i >= (long)currItem.weight*k){
dp[i] = Math.max(dp[i], pdp[i-currItem.weight*k] + (long)currItem.val*k);
}
}
}
for (int k=0; k<=maxW; k++){
pdp[k] = dp[k];
dp[k] = 0;
}
}
}
System.out.println(pdp[maxW]);
}
static class Item{
int val, weight, k;
public Item(int val, int weight, int k){
this.val = val;
this.weight = weight;
this.k = k;
}
}
}
