#include <bits/stdc++.h>
using namespace std;
struct Garbage {int t, f, h;};
int main() {
int D, G;
cin >> D >> G;
vector<Garbage> garbage(G);
for (int i = 0; i < G; ++i) cin >> garbage[i].t >> garbage[i].f >> garbage[i].h;
sort(garbage.begin(), garbage.end(), [](const Garbage& a, const Garbage& b) {
return a.t < b.t;
});
vector<vector<int>> dp(G + 1, vector<int>(D + 1, -1));
dp[0][0] = 10;
int max_time = 0;
for (int i = 0; i < G; ++i) {
int t = garbage[i].t;
int f = garbage[i].f;
int h = garbage[i].h;
for (int j = 0; j <= D; ++j) {
if (dp[i][j] >= t) {
if (j + h >= D) {
cout << t << endl;
return 0;
}
if (j + h <= D) {
dp[i + 1][j + h] = max(dp[i + 1][j + h], dp[i][j]);
}
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + f);
}
}
max_time = max(max_time, dp[i][0]);
}
cout << max_time;
}
