#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int kapasitas, barang;
cin >> kapasitas >> barang;
vector<int> harga(barang), berat(barang), stok(barang);
for (int i = 0; i < barang; i++) {
cin >> harga[i] >> berat[i] >> stok[i];
}
vector<vector<pair<int, int>>> bagianberat(kapasitas + 1);
for (int i = 0; i < barang; i++) {
if (berat[i] <= kapasitas)
bagianberat[berat[i]].push_back({harga[i], stok[i]});
}
vector<pair<int, int>> barangnya;
for (int w = 1; w <= kapasitas; w++) {
sort(bagianberat[w].rbegin(), bagianberat[w].rend());
int bisadipakai = kapasitas / w;
for (auto &it : bagianberat[w]) {
int harga = it.first, stock = it.second;
int yangdiambil = min(stock, bisadipakai);
bisadipakai -= yangdiambil;
for (int j = 1; yangdiambil > 0; j <<= 1) {
int komposisi = min(j, yangdiambil);
yangdiambil -= komposisi;
barangnya.push_back({w * komposisi, harga * komposisi});
}
if (bisadipakai == 0) break;
}
}
vector<ll> dp(kapasitas + 1, 0);
for (auto &it : barangnya) {
int w = it.first, v = it.second;
for (int j = kapasitas; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[kapasitas] << '\n';
}
//dp[j]=maximan hargaue dengan kapasitas maksimal j
