#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<climits>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
// #include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<bitset>
#include<iomanip>
#include<deque>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
// #include<thread>
// #include<chrono>
// #include "mingw.thread.h"
// #include<unordered_set>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// down up right left
int dx[] = { 0, 1, -1, 0};
int dy[] = { 1, 0, 0, -1};
// all compases directions
int ax[] = { -1, -1, 0, 1, 1, 1, 0, -1};
int ay[] = { 0, 1, 1, 1, 0, -1, -1, -1};
int kx[] = { -2, -2, -1, 1, 2, 2, 1, -1};
int ky[] = { -1, 1, 2, 2, 1, -1, -2, -2};
#define valid(x,y,row,col) x>=0 && y>=0 && x<row && y<col
#define pb push_back
#define mp make_pair
#define fs first
#define se second
#define pi 2*acos(0)
#define PI 3.14159265358979323846264338
#define modulo 1000000007
#define SMA 300010
#define MAX 100000010
// #define INT_MAX 2147483647
// #define INT_MIN -2147483648
#define input freopen("input.txt", "r", stdin)
#define output freopen("output.txt", "w", stdout)
#define ms(a,b) memset(a, b, sizeof(a))
#define sc(n) scanf("%d",&n)
#define loop(i,n) for(int i = 0; i<n; i++)
#define nloop(i,n) for(int i = 1; i<=n; i++)
#define prln(n) printf("%d\n",n)
#define prsp(n) printf("%d ",n)
#define pr(n) printf("%d",n)
#define INF 1100000000
#define all(x) (x).begin(), (x).end()
using namespace std;
// using namespace std::chrono;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pint;
// // typedef vector<int> vint;
// // typedef vector<pint> vpint;
// // after input of int dont forget to take getchar() in uva
// // getline() takes complete line.
// // Matrix 45* rotation formula of n*n (i,j) -> (n-1+i-j,i+j) zero based indexing
// // unique function is awesome
// // compiler might replace this with its function
struct item{
ll v, w, k;
};
ll maxValue(vector<item> &items,int n,ll s,vector<vector<ll>> &Mem){
if(n == 0){
return 0;
}
if(Mem[n][s] != -1){
return Mem[n][s];
}
ll maxV = 0;
for(int i = 0; i<=items[n-1].k; ++i){
if(s-i*items[n-1].w >= 0)
maxV = max( maxV, maxValue( items, n-1, s-i*items[n-1].w, Mem)+i*items[n-1].v);
else
return Mem[n][s] = maxV;
}
return Mem[n][s] = maxV;
}
int main(){
ll s;
int n;
cin >> s >> n;
vector<item> items(n);
for(int i = 0; i<n; ++i){
cin >> items[i].v >> items[i].w >> items[i].k;
}
// vector<vector<ll>> Mem(n+1,vector<ll>(s+1,-1));
vector<ll> dp(s+1,0);
sort(items.begin(),items.end(),[](const item &i1,const item &i2){
if(i1.w == i2.w){
return i1.v > i2.v;
}
return i1.w < i2.w;
});
// cout << maxValue( items, n, s, Mem) << "\n";
// dp[i][j] : maxValue can achive using first i items with weight of j
for(int i = 1; i<=n; ++i){
for(int j = s; j>=0; --j){
for(int t = 0; t<=items[i-1].k; ++t){
if(j-t*items[i-1].w >= 0)
dp[j] = max( dp[j], dp[j-t*items[i-1].w] + t*items[i-1].v);
}
}
}
ll ans = 0;
for(int i = 0; i<=s; ++i){
ans = max( ans, dp[i]);
// cout << dp[i] << " ";
}
cout << "\n";
cout << ans << "\n";
return 0;
}
// priority_queue customized
// struct ele{
// ll value, i, j;
// };
// struct myComp{
// constexpr operator()(struct ele const &e1,struct ele const &e2) const noexcept{
// return e1.value > e2.value;
// }
// };
