#include <fstream>
#include <climits>

using namespace std;
ifstream fin ("energii.in");
ofstream fout ("energii.out");

int n, g, i, j, maxim, w[1005], p[1005], d[10005];

int main(){
    fin >> g >> n;
    for (i=1; i<=n; i++){
        fin >> w[i] >> p[i];
    }
    for(i=1; i<=g; i++)
        d[i] = INT_MAX;
    for (i=1; i<=n; i++){
        for (j=0; j<=g; j++){
            if (d[j] != INT_MAX && j + w[i] <= g && d[j+w[i]] > d[j] + p[i]){
                d[j+w[i]] = d[j] + p[i];
            }
        }
    }
    fout << d[g];
    return 0;
}