using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ClassLibrary1
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }


    public class Class1
    {
        static Dictionary<Tuple<long, long>, long> dic = new Dictionary<Tuple<long, long>, long>();

        static long mod = 1000000007;
        static long[] factorial = new long[100001];
        static long[] invFactorial = new long[100001];

        private static void calcFanctorial(long N)
        {
            factorial[0] = 1;
            for(int i=1; i< N+1; i++)
            {
                factorial[i] = factorial[i - 1] * i;
                factorial[i] %= mod;
            }
            invFactorial[N] = inv(factorial[N]);
            for (int i = (int)N; i > 0; i--)
            {
                invFactorial[i - 1] = invFactorial[i] * i % mod;
            }

        }

        static void Main(string[] args)
        {

            var AA = ReadLongArr();
            long H = AA[0];
            long N = AA[1];

            long[][] AB = new long[N][];

            for (int i=0; i<N; i++)
            {
                AB[i] = ReadLongArr();
            }

            var AB2 = AB.OrderBy(a => a[1]).ToArray();

            long[] dp = new long[H+1];

            var point = AB2[0][0];
            var cost = AB2[0][1];
            var index = 0;

            for (int i = 0; i < H+1; i++)
            {

                if (i <= point)
                {
//                    dp[i] = cost;
                }
                else
                {
                    if(index == N-1)
                    {
                        break;
                    }
                    index++;
                    point = AB2[index][0];
                    cost = AB2[index][1];
                }
                dp[i] = cost;
                for (int j = 1; j <= i -j; j++)
                {
                    dp[i] = Math.Min(dp[i], dp[j] + dp[i - j]);
                }
            }

            index = 0;
            for(long i= AB2[0][0] + 1; i<H+1; i++)
            {
                var cc = AB2[0][1] + dp[i - 1];
                for(int k=0; k<N; k++)
                {
                    var pp = i - AB2[k][0];
                    if (pp > 0)
                    {
                        cc = Math.Min(cc, AB2[k][1] + dp[pp]);
                    }
                    else
                    {
                        cc = Math.Min(cc, AB2[k][1]);
                    }

                }

                for (int j=1; j <= i - j; j++)
                {
                    cc = Math.Min(cc, dp[j] + dp[i - j]);
                }
                dp[i] = cc;
            }

            Console.WriteLine(dp[H]);

        }

        private class AB
        {
            long cost;
            long point;
        }


        private static long nCm(long n, long m)
        {
            if (n < m) return 0;

             return (factorial[n] * invFactorial[m] % mod) * invFactorial[n-m] % mod;
        }

        public static long pow(long a, long b, long mod)
        {
            a %= mod;

            if (b <= 0) return 1;
            var t = pow(a, b / 2, mod);
            if ((b & 1) == 0) return t * t % mod;
            return t * t % mod * a % mod;
        }

        public static long Lcm(long a, long b)
        {
            return a * b % mod * inv(Gcd(a, b)) % mod;
        }

        public static long Lcm(long[] a)
        {
            List<long> vect = new List<long>();
            long lcm = 1;
            for (int i = 0; i < a.Count(); i++)
            {
                var factor = a[i] / GcdVector(vect, a[i]);
                vect.Add(factor);
                lcm = lcm * factor % mod;
            }
            return lcm;
        }

        static long GcdVector(List<long> a, long b)
        {
            long ma = 1;
            for (int i = 0; i < a.Count; i++)
                ma = ma * a[i] % b;
            return Gcd(b, ma);
        }

        public static long Gcd(long a, long b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }

        public static long pow(long a, long b) => pow(a, b, mod);
        public static long inv(long a) => pow(a, mod - 2);

        private static char[][] ReadCharMatrix(long h)
        {
            char[][] mtx = new char[h][];
            for(int i=0; i<h; i++)
            {
                var s = ReadString();
                mtx[i] = s.ToCharArray();
            }
            return mtx;
        }

        private static int[][] CreateIntMatrix(long h, long w)
        {
            int[][] mtx = new int[h][];
            for (int i = 0; i < h; i++)
            {
                mtx[i] = new int[w];
            }
            return mtx;
        }


        private static string ReadString()
        {
            return Console.ReadLine();
        }
        private static string[] ReadStringArr()
        {
            return Console.ReadLine().Split(' ');
        }
        private static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadLongArr()
        {
            string[] s = ReadStringArr();
            long[] l = new long[s.Length];
            for(int i=0; i<l.Length; i++)
            {
                l[i] = long.Parse(s[i]);
            }

            return l;
        }
    }

}


Measured memory_bytes: 15188