#include<bits/stdc++.h> using namespace std; int v[100007],w[100007],k[100007]; int dp[2007]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int s,n; cin >> s >> n; for(int i=1;i<=n;++i) cin >> v[i] >> w[i] >> k[i]; for(int i=1;i<=n;++i){ for(int j=s;j>=w[i];--j){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } cout << dp[s]; }