#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 solve()
{
ll s, n; cin >> s >> n;
vector<pair<ll, ll>> items;
rep (i, 0, n) {
ll value, weight, count;
cin >> value >> weight >> count;
ll j(1);
while (j<= count){
ll curr_val = value * j;
ll curr_weight = weight * j;
if (curr_weight > s) break;
items.pb({curr_val, curr_weight});
count -= j;
j *= 2;
}
}
vll dp(s+1, 0);
for (auto item: items) {
vll temp = dp;
ll value = item.first, weight = item.second;
rep (i, weight, s+1){
temp[i] = max(temp[i], dp[i - weight] + value);
}
dp = move(temp);
}
cout << dp[s] << endll;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
