#include <cstdio>
#include <cstring>
const int maxN=100005;
int cash,n,a[15],w[15];
bool dp[maxN],q[maxN];

void zero_one_package(int v){for (int j = cash; j >= v; j--) dp[j]=dp[j]||dp[j-v];}

void complete_package(int v){for (int j = v; j <= cash; j++) dp[j]=dp[j]||dp[j-v];}

void multiple_package(int i)
{
	int k=1;
	while (k<a[i])
	{
		zero_one_package(k*w[i]);
		a[i]-=k;
		k<<=1;
	}
	if (a[i]) zero_one_package(a[i]*w[i]);	
}

int solve()
{
	for (int i = 1; i <= n; i++)
	{		
		if (a[i]==1) zero_one_package(w[i]);
		else if ((a[i]+1)*w[i]>cash) complete_package(w[i]);
		else multiple_package(i);		
	}
	for (int i = cash; i >= 0; i--)	if (dp[i]) return i;	
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	while (~scanf("%d%d",&cash,&n))
	{
		for (int i = 1; i <= n; i++) scanf("%d%d",a+i,w+i);
		memset(dp,0,cash+1);
		dp[0]=true;
		printf("%d\n",solve());
	}
	return 0;
}//poj Accepted	268KB 63MS