#include <stdio.h>
int fun[105],cost[105];
int K[105][105];
//int max(int a,int b ) { return ( a > b )? a : b; }
int fee;
int knapSack( int S, int N,int wei[],int val[] ) {
	int i, w;
//	fee=0;
	//int K[ N + 1 ][ S + 1 ];
 
	for ( i = 0; i <= N; ++i ) {
 
		for ( w = 0; w <= S; ++w ) {
			if ( i == 0 || w == 0 ) {
				K[ i ][ w ] = 0;
			}
			else if ( wei[ i - 1 ] <= w ) {
				if( val[ i - 1 ] + K[ i - 1 ][ w - wei[ i - 1 ] ] > K[ i - 1 ][ w ])
				{K[ i ][ w ] = val[ i - 1 ] + K[ i - 1 ][ w - wei[ i - 1 ] ];
			/*	if(f)
				{fee += wei[i-1];
				f=0;
				printf("fee = %d",fee);*/
 
				}
 
				else
				K[i][w]=K[i-1][w];
			}
 
			else {
				K[ i ][ w ] = K[ i - 1 ][ w ];
			}
		}
	}
	return K[ N ][ S ];
}
int main(void) {
int b,n,i,ans;
	while(1)
	{
		scanf("%d%d",&b,&n);
		if(b==0 && n==0)
		break;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&cost[i],&fun[i]);
		}
 
		ans=knapSack(b,n,cost,fun);
		for(i=1;i<=b;i++)
		{
			if(K[n][i]==ans)
		{	fee=i;
		break;}
		}
		printf("%d %d\n",fee,ans);
	}
	return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CmludCBmdW5bMTA1XSxjb3N0WzEwNV07CmludCBLWzEwNV1bMTA1XTsKLy9pbnQgbWF4KGludCBhLGludCBiICkgeyByZXR1cm4gKCBhID4gYiApPyBhIDogYjsgfQppbnQgZmVlOwppbnQga25hcFNhY2soIGludCBTLCBpbnQgTixpbnQgd2VpW10saW50IHZhbFtdICkgewoJaW50IGksIHc7Ci8vCWZlZT0wOwoJLy9pbnQgS1sgTiArIDEgXVsgUyArIDEgXTsKCglmb3IgKCBpID0gMDsgaSA8PSBOOyArK2kgKSB7CgkKCQlmb3IgKCB3ID0gMDsgdyA8PSBTOyArK3cgKSB7CgkJCWlmICggaSA9PSAwIHx8IHcgPT0gMCApIHsKCQkJCUtbIGkgXVsgdyBdID0gMDsKCQkJfQoJCQllbHNlIGlmICggd2VpWyBpIC0gMSBdIDw9IHcgKSB7CgkJCQlpZiggdmFsWyBpIC0gMSBdICsgS1sgaSAtIDEgXVsgdyAtIHdlaVsgaSAtIDEgXSBdID4gS1sgaSAtIDEgXVsgdyBdKQoJCQkJe0tbIGkgXVsgdyBdID0gdmFsWyBpIC0gMSBdICsgS1sgaSAtIDEgXVsgdyAtIHdlaVsgaSAtIDEgXSBdOwoJCQkvKglpZihmKQoJCQkJe2ZlZSArPSB3ZWlbaS0xXTsKCQkJCWY9MDsKCQkJCXByaW50ZigiZmVlID0gJWQiLGZlZSk7Ki8KCQkJCQoJCQkJfQoJCQkKCQkJCWVsc2UKCQkJCUtbaV1bd109S1tpLTFdW3ddOwoJCQl9CgkJCQoJCQllbHNlIHsKCQkJCUtbIGkgXVsgdyBdID0gS1sgaSAtIDEgXVsgdyBdOwoJCQl9CgkJfQoJfQoJcmV0dXJuIEtbIE4gXVsgUyBdOwp9CmludCBtYWluKHZvaWQpIHsKaW50IGIsbixpLGFuczsKCXdoaWxlKDEpCgl7CgkJc2NhbmYoIiVkJWQiLCZiLCZuKTsKCQlpZihiPT0wICYmIG49PTApCgkJYnJlYWs7CgkJZm9yKGk9MDtpPG47aSsrKQoJCXsKCQkJc2NhbmYoIiVkJWQiLCZjb3N0W2ldLCZmdW5baV0pOwoJCX0KCQkKCQlhbnM9a25hcFNhY2soYixuLGNvc3QsZnVuKTsKCQlmb3IoaT0xO2k8PWI7aSsrKQoJCXsKCQkJaWYoS1tuXVtpXT09YW5zKQoJCXsJZmVlPWk7CgkJYnJlYWs7fQoJCX0KCQlwcmludGYoIiVkICVkXG4iLGZlZSxhbnMpOwoJfQoJcmV0dXJuIDA7Cn0K

NzggMjAgCjI0IDYgCjI0IDggCjEzIDAgCjIzIDUgCjUgMTAgCjEyIDMgCjE0IDEgCjEyIDUgCjEwIDkgCjIxIDEwIAoyMCA1IAoyMCAyIAoxMSAxMCAKMTMgOCAKMTEgMSAKMTAgNyAKMTMgNyAKOCAyIAoyNCA5IAoyMCAwIAowIDAg

78 20 
24 6 
24 8 
13 0 
23 5 
5 10 
12 3 
14 1 
12 5 
10 9 
21 10 
20 5 
20 2 
11 10 
13 8 
11 1 
10 7 
13 7 
8 2 
24 9 
20 0 
0 0