#include <bits/stdc++.h>
using namespace std;
/*DEFINE*/
#define int long long
#define MASK(x) (1LL << (x))
#define all(x) x.begin(), x.end()
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
const int MOD = 1e9 + 7;
/*FUNTION*/
void ckmax(int &a, int b) { a = max(a, b); }
void ckmin(int &a, int b) { a = min(a, b); }
int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b); }
int lcm(int a, int b) { return a/gcd(a,b)*b; }
template<typename ...Args>
void logger(string vars, Args&&... values)
{
cerr << vars << " = ";
string delim = "";
(..., (cerr << delim << values, delim = ", "));
cerr << '\n';
}
int binpow(int a, int b)
{
if (b == 0) return 1;
int X = binpow(a, b / 2);
if (b & 1) return X * X * a;
return X * X;
}
struct item
{
int w, v, c;
};
struct v
{
int w, v;
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
int t = 1;
while (t--)
{
// code here
int n, s; cin >> s >> n;
if (n == 1)
{
cout << -1 << endl;
return 0;
}
map<int, vector<pair<int, int>>> mp;
for (int i=0; i<n; i++)
{
int w, v, k; cin >> v >> w >> k;
mp[w].push_back({v, k});
}
vector<int> dp(s + 1, 0);
for (int w=1; w<=s; w++) if (mp[w].size())
{
int need = s / w;
sort(all(mp[w]));
for (int i=mp[w].size() - 1; i>=0; i--) // LIST ĐỒ VẬT CÓ TRỌNG LƯỢNG LÀ w
{
int v = mp[w][i].first; // giá trị v
int k = mp[w][i].second; // có k đồ vật trọng lượng w
if (need >= k)
{
need -= k;
for (int i=1; i<=k; i++)
{
for (int sum=s; sum>=w; sum--)
{
ckmax(dp[sum], dp[sum - w] + v);
}
}
}
else
{
for (int i=1; i<=need; i++)
{
for (int sum=s; sum>=w; sum--)
{
ckmax(dp[sum], dp[sum - w] + v);
}
}
break;
}
}
}
int cost = 0;
for (int i=0; i<=s; i++)
{
ckmax(cost, dp[i]);
}
cout << cost << endl;
}
return 0;
}
