#include<bits/stdc++.h> 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; }