#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[2][2001];
struct fil{
deque<ll> f, M;
ll size(){
return f.size();
}
ll ma(){
return M.front();
}
void push(ll vl){
while(M.size() && M.back() < vl) // valores iguais precisam (<)
M.pop_back(); // ser colocados todas as vezes que aparecem
f.push_back(vl), M.push_back(vl);
}
void pop(){
if(f.empty()) return;
if(M.front() == f.front()) M.pop_front();
f.pop_front();
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll s, n, ant = 0; cin >> s >> n;
for(ll i = 0; i < n; i++){
ll v, w, q; cin >> v >> w >> q;
vector<fil> fs(w); // preciso construir a primeira pilha
vector<ll> del(w); // delta para cada pilha
for(ll j = 0; j <= s; j++){
ll r = j % w;
fs[r].push(dp[ant][j] - del[r]); // resposta no nó sem colocar nenhum item
dp[1 - ant][j] = fs[r].ma() + del[r];
if(fs[r].size() == q + 1)
fs[r].pop();
del[r] += v; // ultima coisa a fazer
}
ant = 1 - ant;
}
cout << dp[ant][s] << "\n";
}
