#include<algorithm>
#include<vector>
#include<iostream>
#include<cmath>
#include<numeric>
using namespace std ;
using ll = int ;
void solve(){
ll n , k;
cin >> k >> n;
vector<ll>dp(k+1 , 0);
for(int i = 0 ; i < n ; i++){
int price , w , cnt ;
cin >> price >> w >> cnt ;
// Binary Splitting Concept
for(int j = 1 ; cnt > 0 ; j*= 2){
int take = min(j , cnt);
int new_w = w * take ;
int new_price = price * take ;
for(int p = k ; p >= new_w ; p--){
dp[p] = max(dp[p] , dp[p - new_w] + new_price);
}
cnt-=take ;
}
}
cout << dp[k] ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll _t = 1 ;
// scin >> _t ;
while(_t--){
solve();
}
}
