#include <bits/stdc++.h>
using namespace std;
const int N = 1e5, S = 2e3 + 1;
long long V[N], W[N], K[N], n, s, dp[S], ord[N];
template <typename T> void ckmax(T &a, T b) { a = max(a, b); }
int main(){
cin.tie(0) -> ios_base::sync_with_stdio(0);
cin >> s >> n;
if(n == 1)
{
cin >> V[0] >> W[0] >> K[0];
cout << min(K[0], s / W[0]) * V[0];
return 0;
}
for(int i=0;i<n;i++)
{
cin >> V[i] >> W[i] >> K[i];
}
iota(ord, ord + n, 0);
sort(ord, ord + n, [&](int a, int b){ // larger V[i] / W[i]
return V[a] * W[b] > V[b] * W[a];
});
for(int i=0;i<n;i++)
{
for(int j=s;j>=0;j--)
{
int take = min(K[ord[i]], (s - j) / W[ord[i]]);
ckmax(dp[j + take * W[ord[i]]], dp[j] + take * V[ord[i]]);
}
}
// for(int i=0;i<=20;i++){
// cout << i << ": " << dp[i] << "\n";
// }
cout << *max_element(dp, dp + s + 1);
}
