/**
III U U N N DDDD EEEEE RRRR SSSS TTTTT AAAAA N N DDDD I TTTTT N N OOO W W
I U U NN N D D E R R S T A A NN N D D I T NN N O O W W
I U U N N N D D EEEE RRRR SSSS T AAAAA N N N D D I T N N N O O W W W
I U U N NN D D E R R S T A A N NN D D I T N NN O O WW WW
III UUUUU N N DDDD EEEEE R R SSSS T A A N N DDDD I T N N OOO W W
**/
#include <bits/stdc++.h>
using namespace std;
#define ent '\n'
#define F first
#define S second
#define in insert
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define sz(w) w.size()
#define int long long
#define all(w) w.begin(), w.end()
#define BakTR ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int MOD = 998244353, N = 1e3 + 7 , inf = 1e9 + 7, INF = 2e18, LOG = 20 , mod = 1e6 + 7 ;
int dp[2001] ;
void accepted() {
int m , n ;
cin >> m >> n ;
bool ok = 0 ;
if(n == 1) {
ok = 1 ;
}
vector<pair<pair<double, int>, pair<int, int> > > v;
for(int i = 1; i <= n ; i++) {
int x , y , z;
cin >> x >> y >> z ;
v.push_back({{(double)x * 1.0 / y, -x}, {y, z}});
}
sort(v.rbegin(), v.rend()) ;
for(int j = 0; j <= m; j++)
dp[j] = -INT_MAX;
dp[0] = 0;
for(auto i : v) {
int x = -i.first.second, y = i.second.first, z = i.second.second;
int sum = 0;
for(int jj = 1; jj <= min(m, z) ; jj++) {
for(int j = m ; j >= y ; j--) {
dp[j] = max(dp[j] , dp[j - y] + x) ;
}
sum += y;
if(dp[m] > 0 || sum >= 2000)break;
}
}
int mx = -1;
for(int i = 0; i <= m; i++)mx = max(mx, dp[i]);
cout << mx;
}
signed main() {
BakTR
//PLS NeverGiveUp
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T = 1;
//cin >> T;
while (T--) {
accepted();
cout << ent;
}
}
/**
baktr
65868073990A98C52AFDB7A48F4E8D26
**/
