#include<bits/stdc++.h> using namespace std; int main(){ int f[1000]={0},c[1000],w[1000]; int n,v,i,j; scanf("%d %d",&v,&n); for(i=1;i<=n;i++)scanf("%d %d",&c[i],&w[i]); for(i=1;i<=n;i++){ for(j=v;j>=c[i];j--){ f[j]=max(f[j],f[j-c[i]]+w[i]); } } printf("%d",f[v]); return 0; }