#include <bits/stdc++.h>
#ifdef LOCAL
#include <windows.h>
#endif
using namespace std;
#ifdef LOCAL
template<typename T>
void debugPrint(int line, const string& varName, const T& value) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 10);
cerr << "Line " << line << ": " << varName << " = " << value << "\n";
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
#define dbg(x) debugPrint(__LINE__, #x, x)
#endif
#define TestCases int TC; cin >> TC; while (TC--)
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));
}
struct AUTOIOS {
AUTOIOS() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
} autoios;
constexpr int modulo = 1e9 + 7;
mt19937 mt(static_cast<unsigned>(time(nullptr)));
uniform_int_distribution<int> range(0, 2);
template<typename T>
struct CMP {
bool operator() (const T &a, const T &b) const {
return a < b;
}
};
int main() {
int s, n;
cin >> s >> n;
vector<pair<long long, long long>> object;
for (long long i = 1, v, w, k; i <= n; i++) {
cin >> v >> w >> k;
for (int j = 1; j <= k; k -= j, j *= 2) {
if (w * j > 2000) goto next; // 因为背包容量最大是 S，超过它的重量完全没有作用，避免 dp 时使用无效循环
object.push_back({v * j, w * j});
}
if (k) object.push_back({v * k, w * k});
next:;
}
vector<long long> dp(s + 1);
for (auto it : object) {
auto [v, w] = it;
for (int j = s; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[s];
return 0;
}
