/// punch then pray
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)1e5 ;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int block_size = 710;
void InputFile()
{
//freopen("feast.in","r",stdin);
//freopen("feast.out","w",stdout);
//freopen("test.inp","r",stdin);
//freopen("test.out","w",stdout);
}
void FastInput()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int S,n;
int val[maxN],wei[maxN],cop[maxN];
int f[2001];
int g[2001];
int dp[2][2001];
deque<int> dq[2001];
void Read()
{
cin >> S >> n;
for(int i = 1; i <= n; i++)
{
cin >> val[i] >> wei[i] >> cop[i];
cop[i] = min(cop[i],S / wei[i]);
}
/// i == 0;
int i = 0;
for(int rem = 0; rem < wei[i+1]; rem++)
{
while(!dq[rem].empty())
dq[rem].pop_back();
}
for(int j = 0; j <= S; j++)
{
f[j] = dp[0][j] - j / wei[i+1] * val[i+1] ;
int rem = j % wei[i+1];
while(!dq[rem].empty() && f[dq[rem].back()] <= f[j])
{
dq[rem].pop_back();
}
dq[rem].push_back(j);
while(dq[rem].front() + cop[i+1] * wei[i+1] <= j)
{
dq[rem].pop_front();
}
g[j] = f[dq[rem].front()];
}
for(int i = 1; i <= n; i++)
{
int cur = i & 1;
int pre = cur ^ 1;
for(int j = 0; j <= S; j++)
{
dp[cur][j] = dp[pre][j];
if(j >= wei[i])
{
dp[cur][j] = max(dp[cur][j],g[j-wei[i]] + j / wei[i] * val[i]);
}
}
if(i < n)
{
for(int rem = 0; rem < wei[i+1]; rem++)
{
while(!dq[rem].empty())
dq[rem].pop_back();
}
for(int j = 0; j <= S; j++)
{
f[j] = dp[cur][j] - j / wei[i+1] * val[i+1] ;
int rem = j % wei[i+1];
while(!dq[rem].empty() && f[dq[rem].back()] <= f[j])
{
dq[rem].pop_back();
}
dq[rem].push_back(j);
while(dq[rem].front() + cop[i+1] * wei[i+1] <= j)
{
dq[rem].pop_front();
}
g[j] = f[dq[rem].front()];
}
}
}
cout << dp[n&1][S];
}
void Solve()
{
}
int32_t main()
{
FastInput();
//InputFile();
//int sub_type;
//cin >> sub_type;
//Sieve()
int test;
//cin >> test;
test = 1;
while(test--)
{
Read();
Solve();
//Debug();
}
}
////
/////
//////
