#include<stdio.h>

 #define MAX 100

 int we[MAX],p[MAX];

 int ss[];

 int f(int w,int n)

 {

     int i,j;

         for(j=;j<;j++)

             ss[j]=;

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

         for(j=w;j>;j--)

         {

             if(we[i]<=j)

             {

                 if(p[i]+ss[j-we[i]]>ss[j])

                     ss[j]=p[i]+ss[j-we[i]];

             }

         }

     return ss[w];

 }

 int main()

 {

     int n,w,i,j;

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

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

             scanf("%d%d",&we[i],&p[i]);

         printf("%d\n",f(w,n));

     return ;

 }