#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define pll pair<ll,ll>
using namespace __gnu_pbds;
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update>
using ll=long long;
#define in insert
#define pb push_back
struct Node{
ll v;
ll w;
ll k;
ll ind;
bool operator<(const Node &other){
return w<other.w;
}
};
struct Node2{
ll v;
vector<ll>cnt;
};
void solve(){
ll s, n;
cin >> s >> n;
vector<ll> dp(s+1, 0);
for(int i = 0; i < n; i++){
ll v, w, k;
cin >> v >> w >> k;
for(ll p = 1; k > 0; p <<= 1){
ll take = min(p, k);
ll weight = take * w;
ll value = take * v;
for(ll x = s; x >= weight; x--){
dp[x] = max(dp[x], dp[x - weight] + value);
}
k -= take;
}
}
cout << *max_element(dp.begin(), dp.end());
}
int main(){
solve();
return 0;
}
