#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define F first #define S second #define all(x) x.begin(), x.end() #define pii pair<int, int> #define pll pair<long long, long long> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; const int N=1e5+10; const int MAXS = 2001; //const ll mod=998244353; const ll mod=1000000007; const int intinf=2e9; const ll llinf=9e18; const ld eps=2e-7; ll S, n, dp[2][MAXS], v[N], w[N], k[N]; void solve(){ cin >> S >> n; for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> k[i]; for(int i = 1; i <= n; i++){ for(int j = 0; j < w[i]; j++){ multiset<ll> ms; for(int kk = j, cnt = 10, cnt1 = 0; kk <= S; kk += w[i], cnt--, cnt1++){ if(cnt1 > k[i]){ ms.erase(ms.find(dp[(i - 1) % 2][kk - (k[i] + 1) * w[i]] + (cnt + k[i] + 1) * v[i])); //cout << ms.size() << "\n"; //cout << "delete: " << dp[i - 1][kk - (k[i] + 1) * w[i]] + (cnt + k[i] + 1) * v[i] << "\n"; } ms.insert(dp[(i - 1) % 2][kk] + cnt * v[i]); //cout << "add: " << dp[i - 1][kk] + cnt * v[i] << "\n"; dp[i % 2][kk] = *ms.rbegin() - cnt * v[i]; //cout << "value: " << *ms.rbegin() << " " << cnt * v[i] << "\n"; } } } /* for(int i = 1; i <= n; i++){ for(int j = 0; j <= S; j++){ cout << dp[i][j] << " "; } cout << "\n"; } */ cout << dp[n % 2][S] << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t=1; //cin >> t; while(t--) solve(); return 0; }