#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>
#include<cstring>
#include<algorithm>
//using namespace std;
#define int long long
const int N = 1e3 + 5;
struct node {
	int t,h,f;
    bool operator < (node a)const{
        return t < a.t;
    }
} a[105];
int d,g,f[105][N * 25 + 5],sum,ans = 0x3f3f3f3f3f3f3f3f,longest = 10;
void in(int &n) {
	char ch = getchar();
	int f = 1,ans = 0;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f *= -1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0') ans = (ans << 1) + (ans << 3) + ch - '0',ch = getchar();
	n = ans * f;
}

void out(int n) {
	if(n < 0) putchar('-'),n *= -1;
	if(n > 9) out(n / 10);
	putchar(n % 10 + '0');
}
void out(int n,char c) {
	out(n),putchar(c);
}
signed main() {
//	freopen("p.out","w",stdout);
//	freopen("p.in","r",stdin);
	in(d),in(g);
	for(int i = 1; i <= g; i ++) {
		in(a[i].t),in(a[i].f),in(a[i].h);
		sum += a[i].t;
	}
    std::sort(a + 1,a + g + 1);
	memset(f,-0x3f,sizeof(f));
	f[0][10] = 0;
	for(int i = 1; i <= g; i ++) {
		for(int j = sum; j >= a[i].t; j --) {
			if(a[i].f + a[i].t <= j)f[i][j] = std::max(f[i - 1][j] + a[i].h,f[i - 1][j - a[i].f]);
            else f[i][j] = f[i - 1][j] + a[i].h;
			if(f[i][j] < 0) f[i][j] = -0x3f3f3f3f3f3f3f3f;
		}
	}
	//		for(int j = 0;j <= d;j ++){
	//			out(f[i][j],' ');
	//		}
	//		putchar('\n');
	//	}
//	for(int i = 1;i <= g;i ++){
	for(int i = 1; i <= g; i ++) {
		for(int j = 1; j <= sum; j ++) {
			if(f[i][j] >= d) {
				ans = a[i].t,out(ans,'\n');
				return 0;
			};
		}
	}
    for(int i = 1;i <= g;i ++){
        if(longest >= a[i].t) longest += a[i].f;
        else break;
    }
	out(longest,'\n');
	return 0;
}

记录详情