#include <bits/stdc++.h>
#define pb push_back
#define sz size()
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define whatis(x) cout << #x << " is " << x << endl
using namespace std;
typedef long long ll;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
const ll mod = 1e9 + 7;
ll fp(ll x, ll y)
{
if(y == 0) return 1;
ll a = fp(x, y/2);
a = (a * a) % mod;
if(y & 1) a = (a * x) % mod;
return a;
}
//ll comb(ll n, ll r)
//{
// return (fact[n] * fp((fact[r] * fact[n-r]) % mod, mod - 2)) % mod;
//}
ll nxt()
{
ll x;
cin >> x;
return x;
}
int dp[1000100];
void solve()
{
int s,n;
cin >>s>>n;
int v[n];
int w[n];
int k[n];
for (int i=0;i<n;i++){
cin >>v[i]>>w[i]>>k[i];
}
for (int i=0;i<n;i++){
for(int o=0;o<k[i];o++)
for (int j=s;j>0;j--){
if(j-w[i]>0)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout <<dp[s];
}
int main()
{
int T = 1;
// cin >> T;
while(T--)
{
solve();
}
return 0;
}
