#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <set>
#include<queue>
#include <numeric>
#include<bitset>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll MOD = 1e9+7;
const ll MAXV = 100000;
int main(){
ll s,n; cin>>s>>n;
vector<ll>dp(s+1,0);
// vector<tuple<int,int,int>>v(n);
for(int i = 0; i < n; i++){
// cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
ll v,w,k;
cin>>v>>w>>k;
ll cnt = 1;
while(k>0){
ll take ;
if(cnt<=k){
take = cnt;
}
else{take = k;
}
k-=take;
for(ll j=s;j>=take*w;j--){
dp[j] = max(dp[j] , take*v+dp[j-take*w]);
}
cnt << 1;
}}
cout<<dp[s]<<"\n";
}
