#include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<iomanip>

 #include<cstdlib>

 using namespace std;

 const int maxn=;

 const int inf=;

 int L,n;

 int w[maxn],v[maxn],c[maxn];

 void init(){

     scanf("%d%d",&L,&n);

     for(int i=;i<=n;i++)scanf("%d%d",&w[i],&v[i]);

 }

 void work(){

     memset(c,-,sizeof(c));

     c[]=inf;

     for(int i=;i<=n;i++)

         for(int j=L;j>=;j--){

             if(j<w[i])break;

             c[j]=max(c[j],min(c[j-w[i]],v[i]));

         }

     cout<<c[L]<<endl;

 }

 int main(){

     init();

     work();

 }