#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<int> V(N + 1), W(N + 1), K(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> V[i] >> W[i] >> K[i];
}
vector<pair<int, int>> items;
for (int i = 1; i <= N; ++i) {
for (int bit = 0; bit <= (int) floor(log2(K[i]) + 1); ++bit) {
if (K[i] >> bit & 1) {
items.emplace_back(i, bit);
}
}
}
const i64 inf = 1e18;
const int num = (int) items.size();
vector dp(num + 1, vector<i64>(S + 1, -inf));
dp[0][0] = 0;
for (int i = 1; i <= num; ++i) {
auto [idx, bit] = items.at(i - 1);
for (int sum = 0; sum <= S; ++sum) {
dp[i][sum] = dp[i - 1][sum];
i64 opt = (i64) sum - (i64) (1 << bit) * W[idx];
if (opt >= 0) {
dp[i][sum] = max(dp[i][sum], dp[i - 1][opt] + (i64) (1 << bit) * V[idx]);
}
}
}
i64 ans = 0;
for (int sum = 0; sum <= S; ++sum) {
ans = max(ans, dp.back().at(sum));
}
cout << ans << '\n';
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
