#include<bits/stdc++.h>
using namespace std ;
long long knapsack(vector<long long> weights , vector<long long> & prices , long long W) {
int N = weights.size() ;
vector<long long> dp(W + 1,0) ;
for(int i = N - 1 ; i >= 0 ; --i) {
for(int cap = W ; cap >= weights[i] ; --cap) {
dp[cap] = max(dp[cap],prices[i] + dp[cap - weights[i]]) ;
}
}
return dp[W] ;
}
void run_case() {
long long S , N ;
cin >> S >> N ;
if(N == 1) {
long long value , weight , k = 0;
cin >> value >> weight >> k ;
long long take = S / weight ;
k = min(k,take) ;
cout << value * k ;
return ;
}
vector<long long> weights , prices ;
for(int i = 0 ; i < N ; ++i) {
long long value , weight , k = 0 ;
cin >> value >> weight >> k ;
while(k--) {
weights.push_back(weight) ;
prices.push_back(value) ;
}
}
cout << knapsack(weights,prices,S) ;
}
signed main() {
run_case() ;
return 0 ;
}
