#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int ,int>
#define vi vector<int>
#define Harry55 ios::sync_with_stdio(0),cin.tie(0);
#define ff first
#define ss second
void solve(){
int s, n;
cin >> s >> n;
vector<pii> arr;
for(int i = 0 ; i < n ; i++){
int v, w, k, x = 0;
cin >> v >> w >> k;
for(int j = 1 ; j * 2 <= k ; j *= 2){
x += j;
arr.push_back({j * w, j * v});
}
arr.push_back({(k - x) * w, (k - x) * v});
}
vi dp(s + 1, 0);
for(int i = 0 ; i < arr.size() ; i++){
auto [w, v] = arr[i];
for(int j = s ; j >= 0 ; j--){
dp[j] = max(j - w >= 0 ? dp[j - w] + v : 0, dp[j]);
}
}
cout << dp[s];
}
signed main(){
Harry55
int t = 1;
// cin >> t;
while(t--) solve();
}
