import java.util.*;
public class knapsack {
public static void main (String[]args) {
Scanner scan = new Scanner (System.in);
int maxWeight = scan.nextInt();
int itemNumber = scan.nextInt();
Hashtable <Integer, ArrayList<Pair>> itemHash = new Hashtable <Integer, ArrayList<Pair>>();
Triplet [] arr = new Triplet [itemNumber];
for (int i = 0; i < itemNumber; i++) {
int value = scan.nextInt();
int weight = scan.nextInt();
int copyNumber = scan.nextInt();
Triplet addingTriplet = new Triplet (value, weight, copyNumber);
arr[i] = addingTriplet;
}
Arrays.sort(arr);
for (int i = 0; i < itemNumber; i++) {
Triplet t = arr[i];
int value = t.value;
int weight = t.weight;
int copyNumber = t.copyNumber;
Pair addingPair = new Pair (value, copyNumber);
if (itemHash.containsKey(weight) == false) {
itemHash.put(weight, new ArrayList<Pair>());
}
itemHash.get(weight).add(addingPair);
}
Enumeration<Integer> keys = itemHash.keys();
ArrayList<Integer> weights = new ArrayList<Integer>();
while (keys.hasMoreElements()) {
int curWeight = keys.nextElement();
weights.add(curWeight);
ArrayList<Pair> temp = itemHash.get(curWeight);
Collections.sort(temp);
itemHash.put(curWeight, temp);
}
Collections.sort(weights);
/*
for (int i = 0; i < weights.size(); i++) {
ArrayList<Pair> temp = itemHash.get(weights.get(i));
System.out.println(weights.get(i) + ":");
for (int j = 0; j < temp.size(); j++) {
System.out.print("(" + temp.get(j).value + ", " + temp.get(j).copyNumber + ") ");
}
System.out.println("");
}
*/
// Program works so far
// Dp represents the maximum possible value if we have gone through the first i weight groups and have reached a total weight of j
long [][] dp = new long [itemHash.size() + 1][maxWeight + 1];
// Initialization
for (int i = 0; i <= itemHash.size(); i++) {
Arrays.fill(dp[i], Integer.MIN_VALUE);
}
// Base Case
dp[0][0] = 0;
// Gone through counter weight groups
for (int i = 0; i < weights.size(); i++) {
int curWeight = weights.get(i);
ArrayList<Pair> valueCopyNumberList = itemHash.get(curWeight);
// Reached a current total weight of j
for (int j = 0; j <= maxWeight; j++) {
int amountLeft = maxWeight - j;
// Checks if the state has been reached or not
if (dp[i][j] == Integer.MIN_VALUE) {
continue;
}
// Before going through the list, create a transition that skips over this entire weight group
dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
int runningTotal = 0;
long addingTotal = 0;
boolean finished = false;
// Iterate through the weight group
for (int k = 0; k < valueCopyNumberList.size(); k++) {
int curAddingValue = valueCopyNumberList.get(k).value;
int copyNumber = valueCopyNumberList.get(k).copyNumber;
for (int l = 0; l < copyNumber; l++) {
runningTotal += curWeight;
addingTotal += curAddingValue;
if (runningTotal > amountLeft) {
finished = true;
break;
}
// First transition (Finish the weight group right after adding the current value)
dp[i + 1][j + runningTotal] = Math.max(dp[i + 1][j + runningTotal], dp[i][j] + addingTotal);
}
if (finished) {
break;
}
}
}
}
/*
for (int i = 0; i <= itemHash.size(); i++) {
for (int j = 0; j <= maxWeight; j++) {
if (dp[i][j] == Integer.MIN_VALUE) {
System.out.print("- ");
continue;
}
System.out.print(dp[i][j] + " ");
}
System.out.println("");
}
*/
long answer = 0;
for (int i = 0; i <= maxWeight; i++) {
answer = Math.max(answer, dp[itemHash.size()][i]);
}
System.out.println(answer);
}
private static class Triplet implements Comparable <Triplet> {
int value;
int weight;
int copyNumber;
public Triplet (int value, int weight, int copyNumber) {
this.value = value;
this.weight = weight;
this.copyNumber = copyNumber;
}
public int compareTo (Triplet t) {
return (weight - t.weight);
}
}
private static class Pair implements Comparable <Pair> {
int value;
int copyNumber;
public Pair (int value, int copyNumber) {
this.value = value;
this.copyNumber = copyNumber;
}
public int compareTo (Pair p) {
return (p.value - value);
}
}
}
