#include<bits/stdc++.h>
using namespace std;
int main(){
long long kapasitas,barang; cin>>kapasitas>>barang;
vector<int> harga(barang),berat(barang),stok(barang);
vector<long long> 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;
long long beratsemua=quantitas*berat[i],hargatotal=quantitas*harga[i];
for(int k=kapasitas;k>=beratsemua;k--){
dp[k]=max(dp[k],dp[k-beratsemua]+hargatotal);
}
}
}
cout<<dp[kapasitas];
}
//dp[j]=harga termahal dengan maksimal j kg kapasitas
