#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

int h, n, a[1010], b[1010], dp[20010];
int main() {
	scanf("%d %d", &h, &n);
	for (int i = 0; i < n; i++)
		scanf("%d %d", a + i, b + i);
	for (int i = 0; i < h; i++)
		dp[i] = 1e9;
	for (int i = 0; i < n; i++)
		for (int k = 20000; a[i] <= k; k--)
			dp[k - a[i]] = min(dp[k - a[i]], dp[k] + b[i]);
	printf("%d\n", dp[0]);
}