#include <bits/stdc++.h> using namespace std; #define ll long long #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define el '\n' const int MAX_S = 2000; ll dp[MAX_S + 1]; int main() { fast; int S, N; cin >> S >> N; for (int i = 0; i < N; i++) { ll V, W, K; cin >> V >> W >> K; ll c = 1; while (K > 0) { ll t = min(c, K); ll val = V * t; ll weight = W * t; for (int j = S; j >= weight; j--) { dp[j] = max(dp[j], dp[j - weight] + val); } K -= t; c <<= 1; } } cout << dp[S] << el; }