#include <bits/stdc++.h>
using namespace std;
int main(){
int s, n; cin>>s>>n;
vector<int> v(n+1);
vector<int> w(n+1);
vector<int> k(n+1);
vector<vector<int>> dp(s+1, vector<int>(n+1, 0));
for (int i=1; i<=n; i++){
cin>>v[i]>>w[i]>>k[i];
}
cout<<k[1]<<endl;
for (int i=1; i<=n; i++){
for (int m=1; m<=k[i]; m++){
for (int j=0; j<=s; j++){
if(j+w[i]<=s && dp[j][i-1]>0) dp[j+w[i]][i] = max(dp[j+w[i]][i], dp[j][i-1]+v[i]);
if((j+w[i]<=s && dp[j][i]>0) || j==0) dp[j+w[i]][i] = max(dp[j+w[i]][i], dp[j][i]+v[i]);
}
}
//for (int j=1; j<=s; j++) cout<<dp[j][i]<<" ";
//cout<<endl;
}
int cmax=0;
for (int i=1; i<=n; i++){
for (int j=s; j>0; j--){
if(dp[j][i]>0) {
cmax=max(cmax, dp[j][i]); break;
}
}
}
cout<<cmax;
}
