#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll mod=998244353;
struct Item{
ll v;
ll w;
};
ll dp[2002];
void solve(){
ll s, n; cin>>s>>n;
vector<Item> items;
for (ll i=0; i<n; i++){
ll v, w, k;
cin>>v>>w>>k;
for (ll p=1; k>0; p*=2){
ll cnt=min(k, p);
items.push_back({cnt*v, cnt*w});
k-=cnt;
}
}
for(auto &item: items){
for (ll j=s; j>=item.w; j--){
dp[j]=max(dp[j], dp[j-item.w]+item.v);
}
}
cout << dp[s] << '\n';
return;
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
// precomputation
//
const bool multitest=false;
if(multitest){
ll t; cin>>t;
while(t--){
solve();
}
} else {
solve();
}
return 0;
}
