#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Define Template Python++
// Math
const long double PI = acos(-1);
#define intlen(num) to_string(num).size()
// Data Structure and Algorithm
#define all(vec) (vec).begin(),(vec).end()
#define arrsize(arr) sizeof(arr)/sizeof(int)
#define sortarr(arr) sort(arr,arr+arrsize(arr));
#define sortvec(vec) sort(all(vec));
#define minarr(arr) *min_element(arr,arr+arrsize(arr))
#define minvec(vec) *min_element(all(vec))
#define maxarr(arr) *max_element(arr,arr+arrsize(arr))
#define maxvec(vec) *max_element(all(vec))
#define sumarr(arr) accumulate(arr,arr+arrsize(arr),0LL)
#define sumvec(vec) accumulate(all(vec),0LL)
#define reversearr(arr) reverse(arr,arr+arrsize(arr));
#define reversevec(vec) reverse(all(vec));
#define range(i,s,e) for(int i=s;i<e;i++)
#define range2(i,s,e) for(int i=s;i>=e;i--)
#define fors(var,arr) for(auto &var:arr)
// Input Output Manage
#define endl "\n"
#define debug(x) cout<<(#x)<<" : "<<(x)<<endl;
#define debughere cout << "HERE\n";
#define test cout<<"test"<<endl;
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define floatprecision cout<<fixed<<setprecision(9);
#define fileread freopen("input.txt","r",stdin);
#define fileout freopen("output.txt","w",stdout);
#define query cin>>QUERY;while(QUERY--)
#define inputarr(arr,am) int arr[am];fors(num,arr)cin>>num;
#define inputvec(vec,am) vector<int> vec(am);fors(num,vec)cin>>num;
#define input(var) int var;cin>>var;
#define input2(a,b) int a,b;cin>>a>>b;
#define make_edge(a,b) input2(a,b); adj[a].pb(b); adj[b].pb(a);
#define inputs(var) string var;cin>>var;
#define print(var) cout<<(var)<<endl;
#define prints(var) cout<<(var)<<" ";
#define print2(var1,var2) cout<<(var1)<<" "<<(var2)<<endl;
#define printp(paired) cout<<(paired.first)<<" "<<(paired.second)<<endl;
#define printyes(cond) cout<<((cond)?"YES":"NO")<<endl;
#define printarr(arr) fors(num,arr){cout<<num<<" ";};cout<<endl;
#define printmap(hashmap) for(auto[x,y]:hashmap)cout<<x<<" : "<<y<<endl;
#define endline cout<<endl;
// Macro
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pq priority_queue
#define mp make_pair
#define ms multiset
typedef complex<long long> Point;
#define X real()
#define Y imag()
// Oneliner Function
ll sigma(ll num){return (num*(num+1))/2;}
ll gcd(ll a, ll b){return (a==0?b:gcd(b%a,a));}
ll lcm(ll a, ll b){return (a*b)/gcd(a,b);}
ll binpow(ll a,ll b,ll m=INT64_MAX){ll r=1;a%=m;while(b){if(b&1)r=(r*a)%m;a=(a*a)%m;b>>=1;}return r;}
ll invmod(ll a,ll m){return gcd(a,m)==1?binpow(a,m-2,m):0;}
ll lsb(ll x){return log2(x&-x)+1;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define float long double
int QUERY;
// Constant
const int MOD = 1e9+7;
const long long INF = 1e18;
const int maxn = 2e5+5;
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N+10, -1); }
// get representive component (uses path compression)
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
int checkPrime(int n){ // O( sqrt(N))
if(n < 2) return false;
for(int i = 2;i<= sqrt(n);i++){
if(n%i == 0){
return false;
}
}
return true;
}
struct primeStruct{
vector<int> prime_vi;
bool isprime[maxn];
int prime_factorization[maxn];
primeStruct(){
for(int i = 0;i < maxn;i++){
isprime[i] = 1;
prime_factorization[i] = 0;
}
}
void preprocess(){ // O( n log log (n) )
isprime[0] = 0;
isprime[1] = 0;
for(int i = 0;i < maxn;i++){
if(isprime[i]){
int cnt = 2;
prime_factorization[i] = i;
while(cnt * i < maxn){
prime_factorization[i*cnt] = i;
isprime[i*cnt] = 0;
cnt++;
}
}
}
for(int i = 0;i < maxn;i++) if(isprime[i]) prime_vi.pb(i);
}
vector<int> prime_factorization_vi(int n){
vector<int> temp;
while(n!= 1){
temp.pb(prime_factorization[n]);
n/= prime_factorization[n];
}
return temp;
}
};
struct segmentTree{
int segment[1 << 20];
int arr[maxn];
void pointUpdate(int idx, int l, int r, int t, int val){
if(l ==r && r == t) segment[idx] = val;
else if(l > t | r < t) return;
else{
int mid = (l+r)/2;
pointUpdate(2*idx,l,mid,t,val);
pointUpdate(2*idx + 1,mid+1,r,t,val);
segment[idx] = segment[idx*2] + segment[idx*2 + 1]; // fix this if you want to change the type of relation
}
}
int getSum(int idx, int l, int r, int tl, int tr){
if(l > tr || r < tl) return 0;
else if(tl <= l && r <= tr) return segment[idx];
else{
int mid = (l+r)/2;
return getSum(2*idx,l,mid,tl,tr) + getSum(2*idx + 1,mid+1,r,tl,tr);
}
}
};
void open(){
freopen("haybales.in", "r", stdin);
freopen("haybales.out", "w", stdout);
}
struct matrix {
long long mat[205][205] = {0};
matrix friend operator *(const matrix &a, const matrix &b){
matrix c;
for (int i = 0; i < 205; i++) {
for (int j = 0; j < 205; j++) {
c.mat[i][j] = 0;
for (int k = 0; k < 205; k++) {
c.mat[i][j] =(c.mat[i][j]+ a.mat[i][k] * b.mat[k][j])%MOD;
}
}
}
return c;
}
};
matrix matpow(matrix &base, long long n) {
matrix ans = base;
n--;
while (n) {
if(n&1)
ans = ans*base;
base = base*base;
n >>= 1;
}
return ans;
}
void solve(){
int dp[2005][2005];
range(i,0,2005) range(j,0,2005) dp[i][j]= -INF;
input2(s,n)
map<int,vector<pii>> mp;
range(i,1,n+1){
input2(v,w)
input(k)
if(w <= s) mp[w].pb({v,k});
}
dp[0][0] = 0; // the cost of using 0 item to generate a sum of item-weight 0 is 0
int i = 1;
for(auto &[weight,items] : mp){
sort(items.begin(),items.end(),greater<pii>());
range(j,0,s+1){
dp[i][j] = dp[i-1][j];
// we can start simulating
int count_items = 0;
int count_each = 0;
int profit = 0;
int index_type = 0;
while((count_items+1)*weight <= j && index_type < items.size()){
count_items++; // add items
profit += items[index_type].first; // add second one
count_each++;
// if we already used all of them
if(count_each == items[index_type].second){
count_each = 0;
index_type++;
}
// construct to previous
if(dp[i-1][j-(count_items)*weight] != -INF){
// the state can be reached
dp[i][j] = max(dp[i][j],dp[i-1][j-count_items*weight]+ profit);
}
}
}
i++;
}
int ans = -INF;
range(j,0,s+1){
ans = max(ans,dp[i-1][j]);
}
print(ans)
}
int32_t main(){
fastIO
solve();
return 0;
}
