package yrh;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Yrh2 
    {
        public static int n = 0, t_max = 0;
        public static int [] f = new int [11111],t = new int [1111], value = new int [1111];
        public static int ans = -1;
        
        public static void init()
        {
            Scanner sc = new Scanner(System.in);
            t_max = sc.nextInt();
            n = sc.nextInt();
            int [] f = new int [11111];
            int ans = -1;
            Arrays.fill(f, -1);
            f[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                int t = sc.nextInt(),value = sc.nextInt(),j = 0;
                for (j = t_max; j >= t; j--)
                    if (f[j] < f[j-t] + value)
                    {
                        f[j] = f[j-t] + value;
                        if (ans < f[j])
                            ans = f[j];
                    }
            }
            System.out.print(ans);
        }
        
        public static void dfs(int pre, int t_now, int value_now)
        {
            int i = 0;
            f[t_now] = value_now;
            for (i = pre; i <= n; i++)
            {
                if ((t_now + t[i] <= t_max)&&(f[t_now + t[i]] < f[t_now] + value[i]))
                {
                    dfs(i + 1,t_now + t[i],f[t_now] + value[i]);
                }
            }
        }
        public static void Memory_search()
        {
            Scanner sc = new Scanner(System.in);
            t_max = sc.nextInt();
            n = sc.nextInt();
            Arrays.fill(f, -1);
            f[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                t[i] = sc.nextInt();
                value[i] = sc.nextInt();
            }
            dfs(1,0,0);
            for (int i = t_max; i >= 0; i--)
                if (ans < f[i])
                    ans = f[i];
            System.out.print(ans);
        }
        public static void main(String[] arg0)
        {
        //  init();
            Memory_search();
        }
    }