#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
struct Item {
ll v, w;
};
void solve() {
int s, n; cin >> s >> n;
vector<Item> items;
for (int i = 0; i < n; ++i) {
ll v, w, k;
cin >> v >> w >> k;
ll currentK = k;
ll count = 1;
while (currentK > 0) {
ll num = min(currentK, count);
items.push_back({v * num, w * num});
currentK -= num;
count *= 2;
}
}
vector<ll> dp(s + 1, 0);
for (const auto& item : items) {
ll v = item.v;
ll w = item.w;
for (int cw = s; cw >= w; --cw) {
dp[cw] = max(dp[cw], dp[cw - w] + v);
}
}
ll maxVal = 0;
for (int cw = 0; cw <= s; ++cw) {
maxVal = max(maxVal, dp[cw]);
}
cout << maxVal << endl;
}
int main() {
FASTIO;
solve();
return 0;
}
