#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define mp make_pair
#define sz(a) a.size()
#define MOD 1000000007
#define forn(i, n) for (int i = 0; i < n; ++i)
#define INF 1e18
template <typename... T>
void read(T &...args){
((cin >> args), ...);
}
template <typename... T>
void write(T... args){
((cout << args), ...);
}
const vector<pair<int, int>> dirs1 = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
const vector<pair<int, int>> dirs2 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
const int maxN = 100001;
int dp[maxN][2001];
void solve(){
int n,s;
read(s,n);
int v[n], w[n], k[n];
forn(i,n){
read(v[i], w[i], k[i]);
}
dp[0][0] = 0;
for(int i=1;i<=n;++i){
for(int j=1;j<=s;++j){
dp[i][j] = dp[i-1][j];
for(int t=1;t<=k[i-1];++t){
if(j >= t*w[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-t*w[i-1]] + v[i-1]*t);
}
}
}
write(dp[n][s],'\n');
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
solve();
return 0;
}
