// https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
cin.tie(0)->sync_with_stdio(0);
int W,n; cin >> W >> n;
vector<ll> dp(W+1);
for(int i=0; i<n; i++){
ll value; int weight, copies; cin >> value >> weight >> copies;
int cnt = copies;
int take = 1;
while(cnt > 0){
int use = min(take,cnt);
int cost = use * weight;
ll val = ll(use) * value;
for(int x=W; x>=cost; x--){
dp[x] = max(dp[x], dp[x-cost]+val);
}
cnt -= use;
take *= 2;
}
}
cout << dp[W] << '\n';
}
