#include<bits/stdc++.h>
#include <vector>
#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>
#define IO (std::string)""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");
#define NMAX 100
#define SMAX 2000
int n, s;
int v[NMAX], w[NMAX], k[NMAX];
std::vector<int> dp[2];
void citire(){
std::cin >> s >> n;
for(int i = 1; i <= n; i++)
std::cin >> v[i] >> w[i] >> k[i];
dp[0].resize(s + 1);
dp[1].resize(s + 1);
}
int main(){
citire();
for(int i = 1; i <= n; i++){
for(int j = 0; j <= s; j++){
dp[1][j] = dp[0][j];
for(int x = 0; j - w[i]*x >= 0 && x <= k[i]; x++){
dp[1][j] = std::max(dp[1][j], dp[0][j - x*w[i]] + x*v[i]);
}
}
dp[0] = dp[1];
dp[1].clear();
dp[1].resize(s + 1);
}
std::cout << dp[0][s];
return 0;
}
