#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int s, n;
cin >> s >> n;
int dp[s + 1] = {0};
for (int _ = 0;_ < n;_++) {
int v, w, k;
cin >> v >> w >> k;
int cnt = 1;
while (k > 0) {
int temp = min(cnt, k), w1 = w * temp, v1 = v * temp;
for (int i = s;i >= w1;i--) {
dp[i] = max(dp[i], dp[i - w1] + v1);
}
cnt *= 2;
k -= temp;
}
}
// for (int i = 0;i <= s;i++) {
// cout << dp[i] << ' ';
// }
cout << dp[s] << endl;
}
