#include <stdio.h>
#include <limits.h>
int j,s,n,i,v[10001],min,x,y,poz;
int main() {
	FILE *f=fopen("pusculita.in","r");
	FILE *g=fopen("pusculita.out","w");
	fscanf(f,"%d%d",&s,&n);
	min=INT_MAX;
	for(i=1;i<=s;i++)
		v[i]=INT_MAX;
	for(i=1;i<=n;i++) {
		fscanf(f,"%d%d",&x,&y);
		for(j=0;j<=s;j++)
			if(v[j]!=INT_MAX)
				if(v[j]+y<v[j+x])
					v[j+x]=v[j]+y;
	}
	for(i=1;i<=s;i++)
		if(v[i]<min&&v[i]==s) {
			min=v[i];
			poz=i;
		}
	fprintf(g,"%d",poz);
	return 0;
}