#include <iostream>
#include <algorithm>
using namespace std;
 
int n,w;
int a[2000][2000];
 
void knapsack(int wt[], int val[])
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=w;j++)
{
if((i==0)||(j==0))
{
a[i][j]=0;
}
else if(wt[i-1]<=j)
{
if((val[i-1]+a[i-1][j-wt[i-1]])>a[i-1][j])
{
a[i][j]=val[i-1]+a[i-1][j-wt[i-1]];
}
else
{
a[i][j]=a[i-1][j];
}
}
else
{
a[i][j]=a[i-1][j];
}
}
}
}
 
int value(int wt[],int val[])
{
int i=n,j=w,ans=0;
while(i!=0)
{
if(a[i][j]>a[i-1][j])
{
ans+=wt[i-1];
j=j-wt[i-1];
i--;
}
else
{
i--;
}
}
return ans;
}
 
 
int main() {
	int i,ans1,ans2;
	while(scanf("%d %d",&w,&n))
	{
	i=0;
	ans1=0;
	ans2=0;
	if((n==0)&&(w==0))
	{
	break;
	}
	int wt[n],val[n];
	for(i=0;i<n;i++)
	{
	scanf("%d %d",&wt[i],&val[i]);
	}
	knapsack(wt,val);
	ans1=a[n][w];
	ans2=value(wt,val);
	printf("%d %d\n",ans2,ans1);
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG4sdzsKaW50IGFbMjAwMF1bMjAwMF07Cgp2b2lkIGtuYXBzYWNrKGludCB3dFtdLCBpbnQgdmFsW10pCnsKaW50IGksajsKZm9yKGk9MDtpPD1uO2krKykKewpmb3Ioaj0wO2o8PXc7aisrKQp7CmlmKChpPT0wKXx8KGo9PTApKQp7CmFbaV1bal09MDsKfQplbHNlIGlmKHd0W2ktMV08PWopCnsKaWYoKHZhbFtpLTFdK2FbaS0xXVtqLXd0W2ktMV1dKT5hW2ktMV1bal0pCnsKYVtpXVtqXT12YWxbaS0xXSthW2ktMV1bai13dFtpLTFdXTsKfQplbHNlCnsKYVtpXVtqXT1hW2ktMV1bal07Cn0KfQplbHNlCnsKYVtpXVtqXT1hW2ktMV1bal07Cn0KfQp9Cn0KCmludCB2YWx1ZShpbnQgd3RbXSxpbnQgdmFsW10pCnsKaW50IGk9bixqPXcsYW5zPTA7CndoaWxlKGkhPTApCnsKaWYoYVtpXVtqXT5hW2ktMV1bal0pCnsKYW5zKz13dFtpLTFdOwpqPWotd3RbaS0xXTsKaS0tOwp9CmVsc2UKewppLS07Cn0KfQpyZXR1cm4gYW5zOwp9CgoKaW50IG1haW4oKSB7CglpbnQgaSxhbnMxLGFuczI7Cgl3aGlsZShzY2FuZigiJWQgJWQiLCZ3LCZuKSkKCXsKCWk9MDsKCWFuczE9MDsKCWFuczI9MDsKCWlmKChuPT0wKSYmKHc9PTApKQoJewoJYnJlYWs7Cgl9CglpbnQgd3Rbbl0sdmFsW25dOwoJZm9yKGk9MDtpPG47aSsrKQoJewoJc2NhbmYoIiVkICVkIiwmd3RbaV0sJnZhbFtpXSk7Cgl9CglrbmFwc2Fjayh3dCx2YWwpOwoJYW5zMT1hW25dW3ddOwoJYW5zMj12YWx1ZSh3dCx2YWwpOwoJcHJpbnRmKCIlZCAlZFxuIixhbnMyLGFuczEpOwoJfQoJcmV0dXJuIDA7Cn0=

NTAgMTAKMTIgMwoxNSA4CjE2IDkKMTYgNgoxMCAyCjIxIDkKMTggNAoxMiA0CjE3IDgKMTggOSAKCjUwIDEwCjEzIDgKMTkgMTAKMTYgOAoxMiA5CjEwIDIKMTIgOAoxMyA1CjE1IDUKMTEgNwoxNiAyCgowIDAK

50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0