#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <map> #include <set> #include <stack> #include <queue> #include <bitset> #include <numeric> #include <functional> #include <utility> using namespace std; #define ll long long // int helper_right(vector<vector<int> >&ar, int val) { // } // void dfs(vector<vector<int>>&table, vector<vector<int>>&adj, vector<int>&vis, int u, int&cnt) { // vis[u] = 1; // cnt++; // for(int i:table[u]) { // for(int j:adj[i]) { // if(!vis[j]) { // dfs(table, adj, vis, j, cnt); // } // } // } // } int hcf(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } long long findLCM(int a, int b) { return ((long long)a * b) / hcf(a, b); } bool isPallindrome(string&s) { int n = s.size(); int l = 0; int r = n-1; while(l < r) { // cout<<s[l]<<" "<<s[r]<<"\n"; if(s[l] != s[r]) return false; l++; r--; } return true; } void func() { int s, n; cin>>s>>n; vector<array<int, 3> > ar(n); for(int i=0;i<n;i++) { cin>>ar[i][0]>>ar[i][1]>>ar[i][2]; } vector<int> dp(s+1, -1); dp[0] = 0; for(int i=0;i<n;i++) { vector<int> curr = dp; for(int j=0;j<s && (j+ar[i][1]) <= s;j++) { if(dp[j] != -1) { for(int k=0;k<ar[i][2] && (j + ar[i][1]*(k+1)) <= s;k++) { int ind = j + ar[i][1]*(k+1); curr[ind] = max(curr[ind], dp[j] + ar[i][0] * (k+1)); } } } dp = curr; } // cout<<"\n"; // for(int i=0;i<n;i++) { // cout<<ar[i][0]<<" "<<ar[i][1]<<" "<<ar[i][2]<<"\n"; // } int res = -1; for(int i=0;i<=s;i++) res = max(res, dp[i]); cout<<res<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); std::cout.tie(0); int t=1; while(t--) { func(); } // func(); return 0; }