#include <bits/stdc++.h>
 
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
#define ins insert
#define pb push_back
#define mp make_pair
#define sz size
#define rep(i, n) for(int i = 0; i < n; ++i)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%I64d",&n)
#define pdn(n) printf("%d\n",n)
#define plln(n) printf("%I64d\n",n)
#define pd(n) printf("%d ",n)
#define nl() printf("\n")
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef vector<vi> vii;
typedef pair<int, int> pii;
 
int budget, parties;
 
int fun[101], fee[101];
 
int dp[101][501];
 
int solve(int idx, int rembudget) {
	if(rembudget == 0)
		return 0;
	if(rembudget < 0)
		-INF;
	if(idx == 0) {
		if(rembudget >= 0)
			return 0;
		return -INF;
	}
	if(dp[idx][rembudget] != -1)
		return dp[idx][rembudget];
	return dp[idx][rembudget] = max(solve(idx-1, rembudget), fun[idx]+solve(idx-1, rembudget-fee[idx]));
}
 
int main() {
	while((cin >> budget >> parties) && (budget) && (parties)) {
		for(int i = 0; i < 101; ++i)
			for(int j = 0; j < 501; ++j)
				dp[i][j] = -1;
		for(int i = 0; i < parties; ++i) {
			cin >> fee[i] >> fun[i];
		}
		for(int i = 0; i < 501; ++i)
			solve(parties-1, i);
		int ans = solve(parties-1, budget);
		int currmin = INF;
		for(int i = 0; i < 501; ++i) {
			if(dp[parties-1][i] == ans) {
					currmin = i;
					break;
			}
		}
		cout << currmin << " " << ans << endl;
	}
	return 0;	
}	

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIElORiAxMDAwMDAwMDAwCiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBNQVhOIDEwMDAwMDUKI2RlZmluZSBpbnMgaW5zZXJ0CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgc3ogc2l6ZQojZGVmaW5lIHJlcChpLCBuKSBmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKQojZGVmaW5lIHNkKG4pIHNjYW5mKCIlZCIsJm4pCiNkZWZpbmUgc2xsKG4pIHNjYW5mKCIlSTY0ZCIsJm4pCiNkZWZpbmUgcGRuKG4pIHByaW50ZigiJWRcbiIsbikKI2RlZmluZSBwbGxuKG4pIHByaW50ZigiJUk2NGRcbiIsbikKI2RlZmluZSBwZChuKSBwcmludGYoIiVkICIsbikKI2RlZmluZSBubCgpIHByaW50ZigiXG4iKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiB2ZWN0b3I8bGw+IHZpOwp0eXBlZGVmIHZlY3Rvcjx2aT4gdmlpOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKCmludCBidWRnZXQsIHBhcnRpZXM7CgppbnQgZnVuWzEwMV0sIGZlZVsxMDFdOwoKaW50IGRwWzEwMV1bNTAxXTsKCmludCBzb2x2ZShpbnQgaWR4LCBpbnQgcmVtYnVkZ2V0KSB7CglpZihyZW1idWRnZXQgPT0gMCkKCQlyZXR1cm4gMDsKCWlmKHJlbWJ1ZGdldCA8IDApCgkJLUlORjsKCWlmKGlkeCA9PSAwKSB7CgkJaWYocmVtYnVkZ2V0ID49IDApCgkJCXJldHVybiAwOwoJCXJldHVybiAtSU5GOwoJfQoJaWYoZHBbaWR4XVtyZW1idWRnZXRdICE9IC0xKQoJCXJldHVybiBkcFtpZHhdW3JlbWJ1ZGdldF07CglyZXR1cm4gZHBbaWR4XVtyZW1idWRnZXRdID0gbWF4KHNvbHZlKGlkeC0xLCByZW1idWRnZXQpLCBmdW5baWR4XStzb2x2ZShpZHgtMSwgcmVtYnVkZ2V0LWZlZVtpZHhdKSk7Cn0KCmludCBtYWluKCkgewoJd2hpbGUoKGNpbiA+PiBidWRnZXQgPj4gcGFydGllcykgJiYgKGJ1ZGdldCkgJiYgKHBhcnRpZXMpKSB7CgkJZm9yKGludCBpID0gMDsgaSA8IDEwMTsgKytpKQoJCQlmb3IoaW50IGogPSAwOyBqIDwgNTAxOyArK2opCgkJCQlkcFtpXVtqXSA9IC0xOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBwYXJ0aWVzOyArK2kpIHsKCQkJY2luID4+IGZlZVtpXSA+PiBmdW5baV07CgkJfQoJCWZvcihpbnQgaSA9IDA7IGkgPCA1MDE7ICsraSkKCQkJc29sdmUocGFydGllcy0xLCBpKTsKCQlpbnQgYW5zID0gc29sdmUocGFydGllcy0xLCBidWRnZXQpOwoJCWludCBjdXJybWluID0gSU5GOwoJCWZvcihpbnQgaSA9IDA7IGkgPCA1MDE7ICsraSkgewoJCQlpZihkcFtwYXJ0aWVzLTFdW2ldID09IGFucykgewoJCQkJCWN1cnJtaW4gPSBpOwoJCQkJCWJyZWFrOwoJCQl9CgkJfQoJCWNvdXQgPDwgY3Vycm1pbiA8PCAiICIgPDwgYW5zIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsJCn0J

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