#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define emb emplace_back
#define em emplace
#define DB cout<<"\n";system("pause");
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define inf (int)(1e9)
#define INF (ll)(1e18)
#define mod (ll)(1e9 + 7)
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int max_weight , item;
cin>>max_weight>>item;
ll weight[item] , value[item] , total[item];
for(int i=0;i<item;i++) cin>>value[i] >> weight[i] >> total[i];
ll dp[max_weight + 1];
memset(dp,0,sizeof(dp));
for(int i=0;i<item;i++){
for(int j=max_weight ;j >= 0;j--){
for(int k=1;k<=total[i] && j - weight[i] * k >= 0; k++){
dp[j] = max(dp[j] , dp[j - weight[i] * k] + value[i] * k);
}
}
// for(auto x : dp)cout<<x<<" ";
// DB
}
cout<<dp[max_weight];
}
/*
5 4
1 3
5 2
4 2
2 1
5
U 2 5
A 2
A 3
U 1 4
A 3
*/
