#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Global variables for storing the capacity of the knapsack, number of items, value, weight, and number of copies respectively.
int S, N, V, W, K;
// A is an array of vectors, where each vector holds pairs of value and count for items of a particular weight.
vector <pair<int, int>> A[2001];
// dp array to store the maximum value obtainable with a certain weight, answer variable to keep the maximum result.
long long dp[2001], answer;
int main(){
// Input the capacity of the knapsack and number of different types of items
cin >> S >> N;
// Reading the value, weight, and number of copies of each item
for(int i = 0; i < N; i++){
cin >> V >> W >> K;
// Storing value and the number of copies for each weight
A[W].push_back(make_pair(V, K));
}
// Iterate through each possible weight from 1 up to the maximum weight capacity S
for(int i = 1; i <= S; i++){
// If there are items of weight i, sort them by value in descending order (higher value first)
sort(A[i].begin(), A[i].end(), greater<pair<int, int>>());
int index = 0; // Index to track the number of different value groups of the current weight
// Iterate j times where j is the maximum number of items of weight i that can be included without exceeding the capacity
for(int j = 0; j < S / i; j++){
// Check if there are no more items left of the current weight
if(index >= A[i].size()) break;
// Iterate through the knapsack weights from the capacity down to the current item weight
for(int k = S; k >= i; k--){
// Update dp[k] to be the max of itself or the value of including one more of the current item
dp[k] = max(dp[k], dp[k - i] + A[i][index].first);
// Update the answer with the maximum value found so far
answer = max(answer, dp[k]);
}
// Decrement the number of available copies of the current item
A[i][index].second--;
// If all copies of the current item are used, move to the next group of items of the same weight
if(A[i][index].second == 0) index++;
}
}
// Output the maximum value that can be obtained
cout << answer << endl;
return 0;
}
