#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<long long> dp(S + 1, 0); for (int i = 0; i < N; i++) { long long V, W, K; cin >> V >> W >> K; long long totalW = W * K; long long totalV = V * K; if (totalW > S) continue; for (int cap = S; cap >= totalW; cap--) { dp[cap] = max(dp[cap], dp[cap - totalW] + totalV); } } cout << dp[S]; return 0; }