import java.util.*;
import java.io.*;
class Knapsack {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken()); // max weight
int N = Integer.parseInt(st.nextToken()); // number of item types
List<Item> items = new ArrayList<>();
// Read items and expand using binary lifting for large quantities
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int value = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
// Binary lifting: break down large quantities into powers of 2
int k = 1;
while (k < count) {
items.add(new Item(value * k, weight * k));
count -= k;
k *= 2;
}
if (count > 0) {
items.add(new Item(value * count, weight * count));
}
}
// Standard 0/1 knapsack DP on the expanded items
long[] dp = new long[S + 1];
for (Item item : items) {
// Traverse backwards to avoid using the same item multiple times
for (int w = S; w >= item.weight; w--) {
dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);
}
}
System.out.println(dp[S]);
}
static class Item {
long value;
int weight;
Item(long value, int weight) {
this.value = value;
this.weight = weight;
}
}
}
