#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 1e4 + 7;
const long long inf = 1e18;
// dp array to store the maximum value for a given weight
int dp[10000 + 7];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, n;
cin >> m >> n; // Maximum weight and number of items
vector<pair<int, int>> items; // Vector to store {value, weight} pairs
for (int i = 1; i <= n; i++) {
int b, a, c;
cin >> b >> a >> c; // Value, Weight, Count
for (int k = 1; k <= c; k *= 2) {
items.push_back({a * k, b * k});
c -= k;
}
if (c > 0) {
items.push_back({a * c, b * c});
}
}
fill(dp, dp + 10000 + 1, inf); // Fill dp array with infinity
dp[0] = 0;
for (auto &[value, weight] : items) {
for (int j = 10000; j >= weight; j--) {
dp[j] = min(dp[j], dp[j - weight] + value);
}
}
for (int i = 10000; i >= 0; i--) {
if (dp[i] <= m) {
cout << i;
break;
}
}
}
