#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define endl '\n'
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;
#define printmp(a) for(auto x : a) cout << x[0] << ' ' << x[1] << endl;
const int mod = 1e9 + 7;
void solve(){
int s, n;
cin >> s >> n;
vector<int> v(n), w(n), k(n);
for(int i = 0; i < n; i ++)
cin >> v[i] >> w[i] >> k[i];
vector<int> dp(s + 1);
for(int i = 0; i < n; i ++){
for(int j = s; j >= 0; j --){
for(int t = 1; t <= k[i] and j >= t * w[i]; t ++){
dp[j] = max(dp[j], dp[j - t * w[i]] + v[i] * t);
}
}
}
cout << *max_element(all(dp));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
cout << endl;
}
}
