#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <iomanip>
#include <chrono>
using namespace std;
using namespace std::chrono;
void quit() {
cout.flush();
exit(0);
}
const long long md = 1e9+7;
const int mx = 2000;
int main(void){
//freopen("qwer.in", "r", stdin);
//freopen("qwer.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int s, n; cin >> s >> n;
vector<long long> dp(mx+1, -1e15);
dp[0]=0;
for(int i = 0; i < n; i++){
long long v,w,k; cin >> v >> w >> k;
for(int curr = 2000; curr >= 0; curr--){
for(int j = 1; j <= k; j++){
int x = curr-j*w;
if(x >= 0){
dp[curr]=max(dp[curr], dp[x]+v*j);
}
}
}
}
long long ans = 0;
for(int i = s; i >= 0; i--){
ans = max(ans, dp[i]);
}
cout << ans << "\n";
quit();
}
