> #include<cstdio>
> #include<cstring>
> #include<cstdlib>
> #include<iostream>
> #include<algorithm>
> #include<cmath>
> using namespace std;
> #define N 1001000
> #define M 1010
> int f[N];
> int w[M],c[M];
> int n,m;
> 
> void mutipack(int w,int c,int amount){
> 	if (amount * c >= m){
> 		for (int i = c; i<=m; i++){
> 			f[i] = max(f[i - c] + w,f[i]);
> 		}
> 		return;
> 	}
> 	int k = 1;
> 	while (k <= amount){
> 		for (int i = m; i>= k*c; i--){
> 			f[i] = max(f[i],f[i - k*c] + k*w);
> 		}
> 		amount -= k;
> 		k <<= 1;
> 	}
> 	for (int i = m; i>=amount * c; i--){
> 		f[i] = max(f[i],f[i-amount*c] + amount*w);
> 	}
> 	return;
> }
> 
> int main(){
> 	while (scanf("%d",&m) != EOF){
> 		scanf("%d",&n);
> 		for (int i = 1; i<=n; i++){
> 			scanf("%d%d",&c[i],&w[i]);
> 		}	
> 		memset(f,0,sizeof(f));
> 		f[0] = 0;
> 		for (int i = 1; i<=n; i++){
> 			mutipack(w[i],w[i],c[i]);
> 		}
> 		printf("%d\n",f[m]);
> 	}
> 	return 0;	
> }