#include<cstdio>
#include<cstring>
using namespace std;
int n, m, a[5005], f[100005][4505], b[5005];
int ans = 1e9;
int dfs(int k, int s){
	int p, q = 1e9;
	if(f[k][s]) return f[k][s];
	if(s == m){
		return 0;
	}
	if(k > n) return 1e9;
	for(int i = 0; i <= b[k]; i++){
		p = dfs(k + 1, s + i) + a[k] * i;
		if(p < q) q = p;
	}
	return f[k][s] = q;
}
int main(){
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d", &a[i], &b[i]);
	}
	ans = dfs(1, 0);
	printf("%d", ans);
	return 0;
}