// 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, weight, copies; cin >> value >> weight >> copies;
ll cnt = copies;
ll take = 1;
while(cnt > 0){
ll use = min(take,cnt);
ll cost = use * weight;
ll val = use * value;
for(int x=W; x>=cost; x--){
dp[x] = max(dp[x], dp[x-cost]+val);
}
cnt -= use;
take *= 2ll;
}
}
cout << dp[W] << '\n';
}
