import java.io.*;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
StringTokenizer st = new StringTokenizer(br.readLine());
int maxWeight = Integer.parseInt(st.nextToken());
int numItemTypes = Integer.parseInt(st.nextToken());
HashMap<Integer, ArrayList<int[]>> weightMap = new HashMap<>();
for (int i = 0; i < numItemTypes; i++) {
st = new StringTokenizer(br.readLine());
int value = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
int copies = Integer.parseInt(st.nextToken());
if (weightMap.containsKey(weight)) {
weightMap.get(weight).add(new int[] {value, copies});
} else {
ArrayList<int[]> itemArray = new ArrayList<>();
itemArray.add(new int[] {value, copies});
weightMap.put(weight, itemArray);
}
}
long[][] maxVal = new long[maxWeight + 1][weightMap.size() + 1];
int currentWeight = 1;
for (var weightCategory : weightMap.entrySet()) {
ArrayList<int[]> weightList = weightCategory.getValue();
int weight = weightCategory.getKey();
int numWeightsConsidered = 0;
for (int[] weightMod : weightList) {
numWeightsConsidered += weightMod[1];
}
numWeightsConsidered = Math.min(numWeightsConsidered, maxWeight/weight);
Collections.sort(weightList, Comparator.comparingInt(j -> -j[0]));
for (int i = 0; i <= maxWeight; i++) {
maxVal[i][currentWeight] = Math.max(maxVal[i][currentWeight], maxVal[i][currentWeight - 1]);
long valAccrued = maxVal[i][currentWeight - 1];
int totalWeight = i;
int weightType = 0;
int j = 0;
// System.out.println(numWeightsConsidered);
while(j < numWeightsConsidered) {
int numCopies = weightList.get(weightType)[1];
while (j < numWeightsConsidered && numCopies > 0) {
// System.out.println(i + "weight " + j + " " + maxVal[i][currentWeight-1] + " " + numCopies + " " + weightList.get(weightType)[0] + " " + weight);
valAccrued += weightList.get(weightType)[0];
totalWeight += weight;
if (totalWeight <= maxWeight)
maxVal[totalWeight][currentWeight] = Math.max(maxVal[totalWeight][currentWeight], valAccrued);
numCopies--;
j++;
}
weightType++;
if (totalWeight > maxWeight)
break;
}
}
currentWeight++;
}
long maxValue = 0;
int size = weightMap.size();
for (int i = 0; i <= maxWeight; i++) {
maxValue = Math.max(maxValue, maxVal[i][size]);
}
pw.println(maxValue);
br.close();
pw.close();
}
}
