#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll s, n;
cin >> s >> n;
vi v(0);
vi w(0);
rep(i, 0, n){
ll V, W, K;
cin >> V >> W >> K;
ll c = 1;
while(K > c){
v.push_back(c * V);
w.push_back(c * W);
K -= c;
c <<= 1;
}
v.push_back(K * V);
w.push_back(K * W);
}
n = v.size();
vi dp(s + 1, 0);
rep(i, 0, n){
down(j, s + 1, w[i]){
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
ll best = 0;
rep(i, 0, s + 1) best = max(best, dp[i]);
cout << best << endl;
}
