#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;
for(ll j=s;j>=0;j--){
for(ll t= 1;t<=k&&t*w<=j;t++){
dp[j] = max(dp[j] , t*v+dp[j-t*w]);
}
}
}
cout<<dp[s]<<"\n";
}
