/////////////////////////////////////////////////////////////////
//////// Born_To_Laugh - Hughie Do ////////
/////////////////////////////////////////////////////////////////
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=3e5+5;
const int INF=1e9+7;
/*
Idea:
*/
void solve(){
int t ,s;
cin >> s >> t;
vector<pair<int,int>> items;
items.push_back({0,0});
int n=0;
while(t--){
int w, v ,k;
cin >> v >> w >> k;
if(w<=s){
n+=k;
while(k--){
items.emplace_back(make_pair(w,v));
}
}
}
sort(items.begin(), items.end());
vector<vector<int>> dp(n+1, vector<int> (s+1, 0));
/*
dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
*/
dp[0][0]=0;
for(int i=1; i<=n; ++i){
for(int j=0; j<=s; ++j){
if(j-items[i].first >= 0){
dp[i][j]=max(dp[i-1][j], dp[i-1][j-items[i].first] + items[i].second);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
cout << dp[n][s];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
return 0;
}
/*
Use for suggestion:
{
while
}
{
nullptr
sync_with_stdio
false
return
to_string
length
}
{
push_back
pop_back
sort
reverse
begin
end
distance
assign
}
{
insert
erase
lower_bound
upper_bound
binary_search
}
{
first
second
swap
}
{
double
float
unsigned
}
{
unordered_map
pair
vector
deque
string
auto
cout
}
*/
