#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define show(x) cout << x << '\n'
#define showh(x) cout << x << ' '
#define go(i, a, n) for (ll i = a; i < n; i++)
#define gor(i, a, n) for (ll i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf 2000000000000000000LL
auto t1 = chrono::high_resolution_clock::now();
bool prime[100001];
#define maxn 100001
ll expo(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    if (b == 0)
        return 1;
    if (b % 2)
        return ((a % mod) * (expo((a * a) % mod, b / 2) % mod)) % mod;
    return expo((a * a) % mod, b >> 1) % mod;
}
ll mul(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    if (b == 0)
        return 0;
    if (b % 2)
        return ((a % mod) + (mul((a + a) % mod, b / 2) % mod)) % mod;
    return mul((a + a) % mod, b >> 1) % mod;
}

bool ispoweroftwo(ll x)
{
    return x && !(x & (x - 1));
}
ll xorcal(ll n)
{
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    if (n % 4 == 3)
        return 0;
}
void sieve(ll n)
{
    memset(prime, true, sizeof(prime));
    prime[0] = false;
    prime[1] = false;
    for (ll i = 2; i * i <= n; i++)
    {
        if (prime[i] == true)
        {
            for (ll j = i * i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }
}
bool isprime(ll n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    if (n % 2 == 0 or n % 3 == 0)
        return false;

    for (ll i = 5; i * i <= n; i += 6)
    {
        if (n % i == 0 or n % (i + 2) == 0)
            return false;
    }
    return true;
}

ll modinverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m;
        a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

ll gcd(ll a, ll b)
{
    if (a == 0)
    {
        return b;
    }
    return (b % a, a);
}

ll power(ll A, ll B)
{
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;

    ll y;
    if (B % 2 == 0)
    {
        y = power(A, B / 2);
        y = (y * y) % mod;
    }

    else
    {
        y = A % mod;
        y = (y * power(A, B - 1) % mod) % mod;
    }

    return (ll)((y + mod) % mod);
}
bool ispalindrome(string s)
{
    string t = s;
    reverse(t.begin(), t.end());
    if (t == s)
        return true;
    return false;
}
void binary(ll a[], ll n)
{
    gor(i, 0, 64)
    {
        ll k = n >> i;
        a[i] = k & (ll)1;
    }
}
ll countBits(ll n)
{
    if (n == 0)
        return 0;
    return 1 + countBits(n & (n - 1));
}
ll count(ll n)
{
    // if (n == 1)
    //     return 1;
    // return 1 + (2 * count(n / 2));
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    go(i, 2, n + 1)
    {
        dp[i] = 1 + 2 * (dp[i / 2]);
    }
    return dp[n];
}
bool cmp(pair<ll, ll> &a, pair<ll, ll> &b)
{
    if (a.second == b.second)
        return a.first > b.first;
    return a.second < b.second;
}
class atcoder
{
public:
    ll f, s;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll h, n;
    cin >> h >> n;
    atcoder *v = new atcoder[n];
    go(i, 0, n) cin >> v[i].f >> v[i].s;
    ll dp[h + 1];
    go(i, 0, h + 1) dp[i] = inf;
    dp[0] = 0;
    go(i, 1, h + 1)
    {
        go(j, 0, n)
        {
            if (i - v[j].f < 0)
                dp[i] = min(dp[i], v[j].s);
            else
                dp[i] = min(dp[i], dp[i - v[j].f] + v[j].s);
        }
    }
    show(dp[h]);
    auto t2 = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
    clog << "Time taken = " << duration * 1.0 / 1000 << " seconds" << endl;
    return 0;
}

Measured memory_bytes: 384