#include <bits/stdc++.h> using namespace std; struct str { int w, v; }; vector<str> a[1001]; long long dp[1001][1001]; int main() { int n, m; cin >> n >> m; for(int i = 1; i<=m; i++) { int w, v, y; cin >> w >> v >> y; a[y].push_back({w, v}); } for(int i = 1; i<=m; i++) { for(int j = 1; j<=n; j++) { dp[i][j]=dp[i-1][j]; for(int k = 0; k<a[i].size(); k++) { if(j>=a[i][k].w) { dp[i][j]=max(dp[i][j], dp[i-1][j-a[i][k].w]+a[i][k].v); } } } } cout << dp[m][n] << endl; return 0; }