//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long LL;
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18
class p {
public:
int w;
LL v;
int c;
bool operator<(const p &y) {
if (w == y.w) {
return v>y.v;
}
return w < y.w;
}
};
int main() {
int s, n; cin >> s >> n;
vector<p> a;
for (int i = 0; i < n; i++) {
int w; LL v; int c;
cin >> v >> w >> c;
c = min(c, s);
a.push_back({ w,v,c });
}
sort(a.begin(), a.end());
LL nw = -1; LL nc = 0;
vector<pair<LL, LL>> items;
for (int i = 0; i < n; i++) {
if (a[i].w > nw) {
nw = a[i].w;
nc = (s + nw - 1) / nw;
}
for (int j = 0; j < a[i].c; j++) {
if (nc == 0)break;
items.push_back({ a[i].w,a[i].v });
nc--;
}
}
vector<LL> dp(s + 1, -1); dp[0] = 0;
n = items.size();
for (int i = 0; i < n; i++) {
LL w = items[i].first;
LL v = items[i].second;
for (int j = s; j >= 0; j--) {
if (j - w >= 0 and dp[j - w] != -1) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
return 0;
}
