#include <iostream>
using namespace std;
int main() {
    int H, N; cin >> H >> N;
    int dp[H+1];
    const int INF = 1<<30;
    fill(dp, dp+H, INF);
    dp[H] = 0;
    while (N--) {
        int a, b; cin >> a >> b;
        for (int i = H; i >= a; i--)
            dp[i-a] = min(dp[i-a], b + dp[i]);
        for (int i = min(H, a-1); i >= 0; i--) dp[0] = min(dp[0], b + dp[i]);
    }
    cout << dp[0] << endl;
}
