// https://oj.uz/problem/view/NOI18_knapsack
#include<bits/stdc++.h>
using namespace std;
#define ite(i,n) for(int i=0;i<n;i++)
#define itel(i,n) for(ll i=0;i<n;i++)
#define fora(i,a,b) for(int i=a;i<b;i++)
#define fors(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
typedef std::set<ll>::iterator set_p ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define reached cout<<"reached"<<endl
ll MOD=1e9+7;
/*--------------------------------------Printing functions start----------------------------------------------*/
template<typename T>
void print_vec(vector<T>&vec){
for(auto i=vec.begin();i!=vec.end();i++){
cout<<*i<<" ";
}
cout<<"\n";
}
template<typename T>
void print_2Dvec(vector<vector<T>>&vec){
for(int i=0;i<vec.size();i++){
for(int j=0;j<vec[i].size()>0;j++){
cout<<vec[i][j]<<"\t";
}
if(vec[i].size()>0)
cout<<"\n";
}
}
template<typename T, typename S>
void print_pair(pair<T,S> a){
cout<<a.first<<" "<<a.second<<"\n";
}
/*---------------------------------------Printing functions end-----------------------------------------------*/
/*---------------------------------------Graph functions------------------------------------------------------*/
// vector<int>dist(1e5+1,INT_MAX);
// vector<int>par(1e5+1, INT_MAX);
// vector<bool>visited(100001,0);
// vector<vector<int>>graph(2*(1e5)+1);
// template<typename T>
// void g_input(T n,T m){
// for(T i=0;i<m;i++){
// int a,b;
// cin>>a>>b;
// graph[a].push_back(b);
// graph[b].push_back(a);
// }
// }
// void bfs(int s){
// dist[s]=1;
// queue<int>q;
// q.push(s);
// while(!q.empty()){
// int t=q.front();
// q.pop();
// for(int i=0;i<graph[t].size();i++){
// if(dist[graph[t][i]]==INT_MAX){
// dist[graph[t][i]]=dist[t]+1;
// par[graph[t][i]]=t;
// q.push(graph[t][i]);
// }
// }
// }
// }
// void dfs(int n){
// visited[n]=1;
// // cout<<n<<"\n";
// for(int i=0;i<graph[n].size();i++){
// if(!visited[graph[n][i]]){
// dfs(graph[n][i]);
// }
// }
// }
/*---------------------------------------Graph functions------------------------------------------------------*/
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s,n;
cin>>s>>n;
int v,w,k;
vector<pii>list;
list.push_back({0,0});
ite(i,n){
cin>>v>>w>>k;
for(;k>0;k--){
list.push_back({w,v});
}
}
sort(list.begin(), list.end());
n=list.size()-1;
vector<vi>dp(n+1,vi(s+1,0));
for(int i=1;i<n+1;i++){
for(int j=1;j<s+1;j++){
if(j>=list[i].first) dp[i][j]=max(dp[i-1][j-list[i].first]+list[i].second, dp[i-1][j]);
}
}
// print_2Dvec(dp);
cout<<dp[n][s]<<endl;
return 0;
}
