#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);
vector<ll> dp(kapasitas + 1, 0);
for(int i = 0; i < barang; i++){
cin >> harga[i] >> berat[i] >> stok[i];
}
for(int i = 0; i < barang; i++){
int semua = stok[i];
for(int j = 1; semua > 0; j <<= 1){
int quantitas = min(semua, j);
semua -= quantitas;
ll beratsemua = 1LL * quantitas * berat[i];
ll hargatotal = 1LL * quantitas * harga[i];
for(int k = kapasitas; k >= beratsemua; k--){
dp[k] = max(dp[k], dp[k - beratsemua] + hargatotal);
}
}
}
cout << dp[kapasitas] << '\n';
}
