#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
const int INF = 1e9;
const int MOD = 998244353;
const ll MOD2 = 1e9 + 7;
const ll LL_INF = 4e18;
const int MAXN = 1e6 + 1;
void solve() {
int s, n; cin >> s >> n;
vector<pair<ll,ll>> knapsack; //Chứa khối lượng & giá trị
for (int i = 1; i <= n; i++) {
ll v, w, k; cin >> v >> w >> k;
if (k & 1) {
knapsack.push_back({w, v});
k--;
} else {
knapsack.push_back({w,v});
knapsack.push_back({w,v});
k -= 2;
}
while (k) {
if (k & 1) {
knapsack.push_back({w,v});
}
w *= 2; v *= 2; k /= 2;
}
}
vector<ll> dp(s + 1, 0);
for (auto [w, v] : knapsack) {
for (int i = s; i >= w; i--) {
dp[i] = max(dp[i], dp[i-w] + v);
}
}
cout << *max_element(dp.begin(),dp.end()) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// preprocess();
int TC = 1;
// cin >> TC;
while (TC--) solve();
return 0;
}
