#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define maxs 2005
ll dp[maxs] , w[maxn] , v[maxn] , a[maxn];
int main(){
FAST;
ll S;
int n;
cin >> S >> n;
FOR(i , 1 , n) cin >> v[i] >> w[i] >> a[i];
FOR(i , 1 , n){
for(ll k = 1 ; a[i] > 0 ; k *= 2){
int cnt = min(k , a[i]);
a[i] -= cnt;
ll w_i = w[i] * cnt;
ll v_i = v[i] * cnt;
for(ll j = S ; j >= w_i ; j--) dp[j] = max(dp[j] , dp[j - w_i] + v_i);
}
}
cout << dp[S];
}
