#include <iostream>
#include<vector>
#define LL long long
struct items{
LL v, w;
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int s,n;
std::cin>>s>>n;
std::vector<items> Items;
int j=0;
for(int i=0;i<n;++i){
int v,w,k;
std::cin>>v>>w>>k;
int c=1;
while(c<k)
{
k=k-c;
Items.push_back({v*c,w*c});
c=c*2;
}
Items.push_back({v*k,w*k});
}
std::vector<LL> dp(s+1,0);
for(int i=0;i<(int)Items.size();i++)
{
for(int j=s;j>=Items[i].w;j--)
dp[j]=std::max(dp[j],dp[j-Items[i].w]+Items[i].v);
}
std::cout<<dp[s]<<'\n';
return 0;
}
