#include <bits/stdc++.h> using namespace std; int a[1000],b[1000]; bool c[1000]; int w,n; int Max=-1; void f(int s) { if(s-1==n) { int sum1=0,sum2=0; for(int i=1; i<=n; i++) { if(c[i]==true) { sum1+=a[i]; sum2+=b[i]; } if(sum1>w) { sum1-=a[i]; sum2-=b[i]; break; } } if(sum2>Max)Max=sum2; } else { c[s]=true; f(s+1); c[s]=false; f(s+1); } } int main() { cin>>w>>n; for(int i=1; i<=n; i++)cin>>a[i]>>b[i]; f(1); cout<<Max<<endl; return 0; }