#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e4+7;
const long long inf=1e18;
int used[N],p[N],c=0;
//vector<int>v[N];
int dp[1000001];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie();
int m,n;
cin>> m>>n;
int a[n+1],b[n+1];
vector<int>v1,v2;
v1.push_back(0);
v2.push_back(0);
for(int i=1,c;i<=n;i++){
cin>> b[i]>>a[i]>>c;
for(int k=0;k<c;k++){
v1.push_back(a[i]),v2.push_back(b[i]);
}
}
for(int i=0;i<=100000;i++){
dp[i]=inf;
}
dp[0]=0;
for(int i=0;i<v1.size();i++){
for(int j=100000-v2[i];j>=0;j--){
dp[j+v2[i]]=min(dp[j]+v1[i],dp[j+v2[i]]);
}
}
for(int i=100000;i>=0;i--){
if(dp[i]<=m){
cout<< i;
break;
}
}
}
