// Author: Pawan Raj
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
#define F(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ld = long double;
using vi = vector<int>;
using mi = map<int, int>;
using pi = pair<int, int>;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e18 + 1;
/***************************code begins here*****************************/
void solve() {
int h, n, ans = 0;
cin >> h >> n;
assert(1 <= h && h <= 1e4);
assert(1 <= n && n <= 1e3);
vi a(n), b(n);
F(i, n) {
cin >> a[i] >> b[i];
assert(1 <= a[i] && a[i] <= 1e4);
assert(1 <= b[i] && b[i] <= 1e4);
}
vector<int> dp(h + 1, inf);
dp[0] = 0;
F(i, n) {
for (int j = 0; j <= h; j++) {
int k = min(j + a[i], h);
dp[k] = min(dp[k], dp[j] + b[i]);
}
}
ans = dp[h];
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
// assert(1 <= t && t <= 5);
while (t--) {
solve();
}
return 0;
}
Ly8gQXV0aG9yOiBQYXdhbiBSYWoKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIEYoaSwgbikgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCAoeCkuZW5kKCkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxkID0gbG9uZyBkb3VibGU7CnVzaW5nIHZpID0gdmVjdG9yPGludD47CnVzaW5nIG1pID0gbWFwPGludCwgaW50PjsKdXNpbmcgcGkgPSBwYWlyPGludCwgaW50PjsKCmNvbnN0IGludCBOID0gMWU2ICsgNTsKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CmNvbnN0IGludCBpbmYgPSAxZTE4ICsgMTsKLyoqKioqKioqKioqKioqKioqKioqKioqKioqKmNvZGUgYmVnaW5zIGhlcmUqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgaCwgbiwgYW5zID0gMDsKICAgIGNpbiA+PiBoID4+IG47CgogICAgYXNzZXJ0KDEgPD0gaCAmJiBoIDw9IDFlNCk7CiAgICBhc3NlcnQoMSA8PSBuICYmIG4gPD0gMWUzKTsKCiAgICB2aSBhKG4pLCBiKG4pOwoKICAgIEYoaSwgbikgewogICAgICAgIGNpbiA+PiBhW2ldID4+IGJbaV07CiAgICAgICAgYXNzZXJ0KDEgPD0gYVtpXSAmJiBhW2ldIDw9IDFlNCk7CiAgICAgICAgYXNzZXJ0KDEgPD0gYltpXSAmJiBiW2ldIDw9IDFlNCk7CiAgICB9CgogICAgdmVjdG9yPGludD4gZHAoaCArIDEsIGluZik7CgogICAgZHBbMF0gPSAwOwoKICAgIEYoaSwgbikgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDw9IGg7IGorKykgewogICAgICAgICAgICBpbnQgayA9IG1pbihqICsgYVtpXSwgaCk7CiAgICAgICAgICAgIGRwW2tdID0gbWluKGRwW2tdLCBkcFtqXSArIGJbaV0pOwogICAgICAgIH0KICAgIH0KCiAgICBhbnMgPSBkcFtoXTsKCiAgICBjb3V0IDw8IGFucyA8PCAnXG4nOwp9CgppbnQzMl90IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwogICAgY291dC50aWUoMCk7CgogICAgaW50IHQgPSAxOwogICAgLy8gY2luID4+IHQ7CiAgICAvLyBhc3NlcnQoMSA8PSB0ICYmIHQgPD0gNSk7CgogICAgd2hpbGUgKHQtLSkgewogICAgICAgIHNvbHZlKCk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=