#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);
		fee=0;
		if(ans!=0)
		{for(i=1;i<=b;i++)
		{
			if(K[n][i]==ans)
		{	fee=i;
		break;}
		}}
		printf("%d %d\n",fee,ans);
	}
	return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CmludCBmdW5bMTA1XSxjb3N0WzEwNV07CmludCBLWzEwNV1bMTA1XTsKLy9pbnQgbWF4KGludCBhLGludCBiICkgeyByZXR1cm4gKCBhID4gYiApPyBhIDogYjsgfQppbnQgZmVlOwppbnQga25hcFNhY2soIGludCBTLCBpbnQgTixpbnQgd2VpW10saW50IHZhbFtdICkgewoJaW50IGksIHc7Ci8vCWZlZT0wOwoJLy9pbnQgS1sgTiArIDEgXVsgUyArIDEgXTsKCglmb3IgKCBpID0gMDsgaSA8PSBOOyArK2kgKSB7CgkKCQlmb3IgKCB3ID0gMDsgdyA8PSBTOyArK3cgKSB7CgkJCWlmICggaSA9PSAwIHx8IHcgPT0gMCApIHsKCQkJCUtbIGkgXVsgdyBdID0gMDsKCQkJfQoJCQllbHNlIGlmICggd2VpWyBpIC0gMSBdIDw9IHcgKSB7CgkJCQlpZiggdmFsWyBpIC0gMSBdICsgS1sgaSAtIDEgXVsgdyAtIHdlaVsgaSAtIDEgXSBdID4gS1sgaSAtIDEgXVsgdyBdKQoJCQkJe0tbIGkgXVsgdyBdID0gdmFsWyBpIC0gMSBdICsgS1sgaSAtIDEgXVsgdyAtIHdlaVsgaSAtIDEgXSBdOwoJCQkvKglpZihmKQoJCQkJe2ZlZSArPSB3ZWlbaS0xXTsKCQkJCWY9MDsKCQkJCXByaW50ZigiZmVlID0gJWQiLGZlZSk7Ki8KCQkJCQoJCQkJfQoJCQkKCQkJCWVsc2UKCQkJCUtbaV1bd109S1tpLTFdW3ddOwoJCQl9CgkJCQoJCQllbHNlIHsKCQkJCUtbIGkgXVsgdyBdID0gS1sgaSAtIDEgXVsgdyBdOwoJCQl9CgkJfQoJfQoJcmV0dXJuIEtbIE4gXVsgUyBdOwp9CmludCBtYWluKHZvaWQpIHsKaW50IGIsbixpLGFuczsKCXdoaWxlKDEpCgl7CgkJc2NhbmYoIiVkJWQiLCZiLCZuKTsKCQlpZihiPT0wICYmIG49PTApCgkJYnJlYWs7CgkJZm9yKGk9MDtpPG47aSsrKQoJCXsKCQkJc2NhbmYoIiVkJWQiLCZjb3N0W2ldLCZmdW5baV0pOwoJCX0KCQkKCQlhbnM9a25hcFNhY2soYixuLGNvc3QsZnVuKTsKCQlmZWU9MDsKCQlpZihhbnMhPTApCgkJe2ZvcihpPTE7aTw9YjtpKyspCgkJewoJCQlpZihLW25dW2ldPT1hbnMpCgkJewlmZWU9aTsKCQlicmVhazt9CgkJfX0KCQlwcmludGYoIiVkICVkXG4iLGZlZSxhbnMpOwoJfQoJcmV0dXJuIDA7Cn0K

NTAgMTAKMTIgMwoxNSA4CjE2IDkKMTYgNgoxMCAyCjIxIDkKMTggNAoxMiA0CjE3IDgKMTggOSAKCjUwIDEwCjEzIDgKMTkgMTAKMTYgOAoxMiA5CjEwIDIKMTIgOAoxMyA1CjE1IDUKMTEgNwoxNiAyCgowIDA=

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