#include<iostream>
#include<stdio.h>
#include<cstring>
 
#define max1 10000
 
using namespace std;
 
struct node
{
	int fee, fun;
};
 
 
int max(int x, int y)
{
	return x>y?x:y;
}
 
 
int a[2][max1];
node dp[max1];
int p, n;
 
 
node solve(int pos, int cur)
{	
	if(pos == n)
	{
		return (node){cur, 0};
	}
 
	if(cur+a[0][pos]<=p)
	{
		node l = solve(pos+1, cur+a[0][pos]);
		node r = solve(pos+1, cur);
 
		if(l.fun + a[1][pos] > r.fun)
		{
			return (node){l.fee, l.fun + a[1][pos]};
		}
 
		else
		{
			return (node){r.fee, r.fun};
		}		
	}
 
	if(cur+a[0][pos]>p)
	{
		return solve(pos+1, cur);
	}
 
	//else 
	return (node){cur, 0};
}
 
 
int main()
{
	//freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_PARTY.txt", "r", stdin);
 
	while(1)
	{
		scanf("%d %d", &p, &n);
 
		if(p==0 && n==0)
		break;
 
		for(int i=0; i<n; i++)
		{
			scanf("%d %d", &a[0][i], &a[1][i]);
		}
 
		node ans = solve(0, 0);
 
		printf("%d %d\n", ans.fee, ans.fun);
	}
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPGNzdHJpbmc+CgojZGVmaW5lIG1heDEgMTAwMDAKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7CglpbnQgZmVlLCBmdW47Cn07CgoKaW50IG1heChpbnQgeCwgaW50IHkpCnsKCXJldHVybiB4Pnk/eDp5Owp9CgoKaW50IGFbMl1bbWF4MV07Cm5vZGUgZHBbbWF4MV07CmludCBwLCBuOwoKCm5vZGUgc29sdmUoaW50IHBvcywgaW50IGN1cikKewkKCWlmKHBvcyA9PSBuKQoJewoJCXJldHVybiAobm9kZSl7Y3VyLCAwfTsKCX0KCglpZihjdXIrYVswXVtwb3NdPD1wKQoJewoJCW5vZGUgbCA9IHNvbHZlKHBvcysxLCBjdXIrYVswXVtwb3NdKTsKCQlub2RlIHIgPSBzb2x2ZShwb3MrMSwgY3VyKTsKCQkKCQlpZihsLmZ1biArIGFbMV1bcG9zXSA+IHIuZnVuKQoJCXsKCQkJcmV0dXJuIChub2RlKXtsLmZlZSwgbC5mdW4gKyBhWzFdW3Bvc119OwoJCX0KCQkKCQllbHNlCgkJewoJCQlyZXR1cm4gKG5vZGUpe3IuZmVlLCByLmZ1bn07CgkJfQkJCgl9CgkKCWlmKGN1cithWzBdW3Bvc10+cCkKCXsKCQlyZXR1cm4gc29sdmUocG9zKzEsIGN1cik7Cgl9CgkKCS8vZWxzZSAKCXJldHVybiAobm9kZSl7Y3VyLCAwfTsKfQoKCmludCBtYWluKCkKewoJLy9mcmVvcGVuKCJDOlxcVXNlcnNcXFNocmFleWFzXFxEb2N1bWVudHNcXHBnXFxwcl9hZ1xccHJhZ19QQVJUWS50eHQiLCAiciIsIHN0ZGluKTsKCQoJd2hpbGUoMSkKCXsKCQlzY2FuZigiJWQgJWQiLCAmcCwgJm4pOwoJCQoJCWlmKHA9PTAgJiYgbj09MCkKCQlicmVhazsKCQkKCQlmb3IoaW50IGk9MDsgaTxuOyBpKyspCgkJewoJCQlzY2FuZigiJWQgJWQiLCAmYVswXVtpXSwgJmFbMV1baV0pOwoJCX0KCQkKCQlub2RlIGFucyA9IHNvbHZlKDAsIDApOwoJCQoJCXByaW50ZigiJWQgJWRcbiIsIGFucy5mZWUsIGFucy5mdW4pOwoJfQp9

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