#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<long long>
#define pb push_back
#define endll "\n"
#define vvll vector<vector<long long>>
const int MOD = 1e9 + 7;
#define rep(i, a , n) for (int i = a; i < (n); i++)
#define nrep(i, n , a) for (int i = n-1; i >= (a); i--)
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
template<typename K, typename V>
void dbg_out(const map<K, V>& m) {
cerr << "{ ";
for (const auto& pair : m) {
cerr << "(" << pair.first << ", " << pair.second << ") ";
}
cerr << "}";
}
template<typename T>
void dbg_out(const set<T>& s) {
cerr << "{ ";
for (const auto& elem : s) {
cerr << elem << " ";
}
cerr << "}";
}
template<typename T>
void dbg_out(const vector<T>& v) {
cerr << "[ ";
for (const auto& elem : v) {
cerr << elem << " ";
}
cerr << "]";
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
void solve()
{
ll s , n ; cin >> s >> n;
vll prize(n) , weight(n) , qty(n);
for(int i = 0 ; i < n ; i++)
{
cin >> prize[i] >> weight[i] >> qty[i];
qty[i] = min(qty[i] , s/weight[i]);
}
vll dp(s+1);
vll weightt , prizz;
dp[s] = 0;
rep(idx, 0, n)
{
ll v = prize[idx], w = weight[idx], k = min(qty[idx], s / w);
for (ll p = 1; k > 0; p <<= 1)
{
ll take = min(p, k);
weightt.pb(take * w);
prizz.pb(take * v);
k -= take;
}
}
for(ll j = 0 ; j < weightt.size() ; j++)
{
for(ll i = s ; i >= 0 ; i--)
{
if(i >= weightt[j])
dp[i] = max(dp[i - weightt[j]] + prizz[j], dp[i]);
}
}
cout << dp[s];
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
auto start = chrono::high_resolution_clock::now();
int tt = 1; //cin >> tt;
while(tt--)
solve();
auto end = chrono::high_resolution_clock::now();
chrono::duration<double> duration = end - start;
//cout << "Time taken: " << duration.count() << " seconds" << endl;
return 0;
}
