#include <bits/stdc++.h>
#define int long long
using namespace std;
int s,n;
vector<int> value, weight, copies;
void solve(){
cin>>s>>n;
value.resize(n+1);
copies.resize(n+1);
weight.resize(n+1);
for(int i=0;i<n;i++){
cin>>value[i]>>weight[i]>>copies[i];
}
vector<pair<int,int>> new_items;
for(int i=0;i<n;i++){
for(int j=1;copies[i]>0;j *= 2){
int group_size = min(copies[i],j);
new_items.push_back({j*weight[i], j*value[i]});
copies[i] -= group_size;
}
}
vector<int> dp(s+1,0);
for(int i=0;i<new_items.size();i++){
for(int j=s;j>=new_items[i].first;j--){
dp[j] = max(dp[j], new_items[i].second + dp[j - new_items[i].first]);
}
}
cout<<dp[s]<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n_test = 1;
// cin>>n_test;
while(n_test--){
solve();
}
}
