#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
#define ln '\n'
struct Item {
int value;
int weight;
int count;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s{}, n{};
cin >> s >> n;
int v{}, w{}, c{};
vector<Item> items;
for (int i = 0; i < n; ++i) {
cin >> v >> w >> c;
items.push_back({v, w, c});
}
vector<ll> dp(s+1, 0);
for (int i = 0; i < n; ++i) {
for (int k = 1; items[i].count > 0; k *= 2) {
int amount = min(k, items[i].count);
for (int j = s; j >= items[i].weight * amount; j--) {
dp[j] = max(dp[j], dp[j - items[i].weight * amount] + (ll)items[i].value * amount);
}
items[i].count -= amount;
}
}
cout << dp[s] << ln;
return 0;
}
