/*
.;;;;:
:::::::;
;::::::;
:;;;;.
;:::;
;:::::;; ;;;
::::::::::;; ;:::
;:::::::::::;;: .;;:::
.;::::::::::::::;;. .:.:::: ;;;:::;;;
:;:::::::::::::::::;;. :. .::::....: :;;::::::::;
;::::::::::....:::::::;;;;;;;;;;: .:... ....:..: .;;::::::::::::;
:;::::::::........::::::::::::::. :. .. ... . .....;;;:::::::::::::::;
;::::::::..........::::::::::::: .... ..... .....:::::::::::::::::;:
.;:::::::...........:::::::::::: :.. ... ...........:::::::::::::::;.
......................::::::::::: .. .... ..............:::::::::::;
..........:::.......:::::::::::::. . .. .... ............:::::::::;
..........::::::::::::::::.......: .:.... ... ........ .: ::::::;;
........:::::::::::::...........:. ::. .... .... .... .: .::::;:
.......:::::::::::::..............::. .::.. .. .... .:..:::;:
...::::::::::::::::..:::....::....::::. :.... .... .... : ::.
;::::::::::::::::::..::.....:::...::::::::. .:. ... ..... .. .
:;::::::::;; .;:::::............::::::::::: :.... ... .. :.:
;:::::::;. ;;:::.......:::::;;;;..;;;::. :.... .... ...:
;:::::;: .;;::::::;;;;. ;;:... .. .. .:. .
;:::::: :;;: .;:: ....... .:. :
;::::; ;. ;;:: :::.. .:;:
;;::;: :;;;;;; .;::::::::::::;
;::;: .;;;;;;; :;::::::::::::
.;:;: .::;;;;; .;::::::::::;.
.;;;.....;;;;;; ... .;:::::::::;.
;;:.... .:. ;;;;;; :;::::::::;.
:;:......... ..... ;:::::::;:
............. .. ...... :;:::::;:
................... .;;;. .:;. ;;:::;;:
.. ....... ..:;;:;; ;: :;::;;:
;.:::.. ..........:;;;;; .;...:.;;;;;. .
:;:;.................;.;:; ;::::::::: ;;;:::
.;....:........;; ;;:::; .:::::;;:::;.:::. .;:::::::
.:...:; ;..:.:.:::.:;;;:::. :;:: : ..:.:. .;:::::
::.........;;+:....:; .:..:: .::..; ;::;:;;:
;:...........::;;;;;: .:: .; ::..:. :. ;:::;. :.
::::::...;. :::: ..;;;. ;. ;;:::;.
.. ::.;:.;: .::;;; ;;;:::;;.
::.; :;;;;:::........; ;:::;:
.;...::::........;:.....:; ;:
*/
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define rev(i,b,a) for(int i=b; i>=a; --i)
#define pii pair<ll,ll>
using namespace std;
const int maxN = 1e6 + 7;
const ll inf = 1e9 + 7;
const ll moreinf = 1e16 + 7;
struct data{
ll V,W,K;
}a[maxN];
int n,s;
ll cur[5002], pre[5002];
vector<pii> item[2002];
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> s >> n;
rep(i,1,n) cin >> a[i].V >> a[i].W >> a[i].K;
rep(i,1,n){
item[a[i].W].emplace_back(a[i].V, a[i].K);
}
rep(i,1,s){
sort(begin(item[i]),end(item[i]), [](pii a, pii b)->bool{
return a.first > b.first;
});
}
vector<pii> use_item;
use_item.emplace_back(0,0);
rep(weight,1,s){
int cnt = 0;
for(auto it:item[weight]){
rep(i,1,it.second){
++cnt;
use_item.emplace_back(it.first,weight);
if(cnt>=s/weight) break;
}
if(cnt>=s/weight) break;
}
}
rep(i,1,use_item.size()-1){
rep(j,0,s){
// f[i][j] = f[i-1][j];
// if(j>=use_item[i].second) f[i][j] = max(f[i][j], f[i-1][j-use_item[i].second] + use_item[i].first);
cur[j] = pre[j];
if(j>=use_item[i].second) cur[j] = max(cur[j], pre[j-use_item[i].second] + use_item[i].first);
}
rep(j,0,2000){
pre[j] = cur[j];
cur[j] = 0;
}
}
ll maxx = 0;
rep(i,0,2002) maxx = max(maxx,pre[i]);
cout << maxx;
return 0;
}
