#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define mp make_pair
template <class T>
void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "\b}"; }
template <class T>
istream& operator>>(istream& in, vector<T>& v)
{
for(auto&i:v)
cin>>i;
return in;
}
#define MOD 1000000007
#define EPS 1e-6f
#define PI 3.1415926535897932384626433832795
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;
const int MAX_S = 2e3;
int dp[MAX_S+2];
bool dp2[MAX_S+2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("sumdiv.in","r",stdin);
//freopen("sumdiv.out","w",stdout);
int s, n;
cin >> s >> n;
vi w(n);
vi v(n);
vi k(n);
f(i,0,n)
{
cin >> v[i] >> w[i] >> k[i];
}
dp2[0] = true;
f(i,0,n)
{
f(j,0,min(k[i], s / w[i]))
{
rf(x,s+1,0)
{
if (x - w[i] < 0)
continue;
if (dp2[x - w[i]])
{
dp2[x] = true;
dp[x] = max(dp[x], v[i] + dp[x-w[i]]);
}
}
}
}
int ans = 0;
cf(i,0,s)
ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}
