import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public 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());
int N = Integer.parseInt(st.nextToken());
long[][] dp = new long[N+1][S+1];
// dp(i, j) = using the first i weights, with an upper bound of j capacity - what is the best
// price
long[][] items = new long[N+1][3];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
items[i][0] = Long.parseLong(st.nextToken());
items[i][1] = Long.parseLong(st.nextToken());
items[i][2] = Long.parseLong(st.nextToken());
}
for (int i = 1; i <= N; i++) {
long pi = items[i][0];
long wi = items[i][1];
long ki = items[i][2];
for (int j = 1; j <= S; j++) {
for (int k = 0; k <= j/((int)wi) && k <= ((int) ki); k++) {
dp[i][j] = Math.max(Math.max(dp[i][j], dp[i-1][j]),
dp[i-1][j-k*((int)wi)] + pi*((long) k));
}
}
}
System.out.println(dp[N][S]);
}
}
