#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pb push_back
#define F first
#define S second
const int N = 2e5 + 5;
int dp[N] , a[N] , b[N] , k[N];
void solve()
{
/*
20
11 19
10 10
10 10
9 3
dp[w] --- en coxu w cekisi ucun max value
*/
int n , s;
cin >> s >> n;
vector<pair<int , int> > v;
for(int i = 0; i < n; i++){
cin >> b[i] >> a[i] >> k[i];
k[i] = min(k[i] , s / a[i]);
int j = 1;
while(k[i] > 0){
v.pb({a[i] * min(k[i] , j) , b[i] * min(k[i] , j)});
k[i] -= j;
j *= 2;
}
}
/*
n * k * s
k ni min sayda ededlerin cemi seklinde yazki
1 . .... k ya
3 kq
10 man
7 dene
3 kq
10 man
6 kq
20 man
12 kq
40 man
100
3 kq
10 man
6 kq
20 man
12 kq
40 man
8
16
32
37
*/
for(auto i : v){
int w = i.F , v = i.S;
for(int j = s; j >= w; j--){
dp[j] = max(dp[j] , dp[j - w] + v);
}
}
cout << dp[s] << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--)
solve();
}
