#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