#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];
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];
}
for(int i=0;i<n;i++)
{
for(int j=s;j>=0;j--)
{
for(long long k=1;k<=K[i];k++)
{
if(j - k * W[i] >= 0)
dp[j] = max(dp[j], dp[j - k * W[i]] + k * V[i]);
}
}
}
// for(int i=0;i<=20;i++){
// cout << i << ": " << dp[i] << "\n";
// }
cout << *max_element(dp, dp + s + 1);
}
