# include <cstdio>
# include <algorithm>
# include <cstring>
# define DEBUG printf
using namespace std;
int Budget, Total, Entry [100], Fun [100], DPTable [101][2501], MaxFun, MinEntry, i, j;
int main()
{
//freopen ("Input.txt", "r", stdin);
//freopen ("Output.txt","w", stdout);
scanf ("%d%d", &Budget, &Total);
while (Budget && Total)
{
for (i = 0; i < Total; i++) scanf ("%d%d", &Entry [i], &Fun [i]);
memset (DPTable, -1, sizeof DPTable);
for (i = 0; i <= Total; i++) DPTable [i][0] = 0;
for (i = 0; i <= Budget;i++) DPTable [0][i] = 0;
MaxFun = -1;
for (i = 1; i <= Total; i++)
for (j = 1; j <= Budget; j++)
{
DPTable [i][j] = DPTable [i-1][j];
if (j - Entry [i-1] >= 0 && DPTable [i-1][j-Entry[i-1]] != -1)
{
DPTable [i][j] = max (DPTable [i-1][j], DPTable [i-1][j-Entry[i-1]] + Fun [i-1]);
if (DPTable [i][j] > MaxFun || (DPTable [i][j] == MaxFun && j < MinEntry))
{
MaxFun = DPTable [i][j]; MinEntry = j;
}
}
}
printf ("%d %d\n", MinEntry, MaxFun);
scanf ("%d%d", &Budget, &Total);
}
return 0;
}
IyBpbmNsdWRlIDxjc3RkaW8+CiMgaW5jbHVkZSA8YWxnb3JpdGhtPgojIGluY2x1ZGUgPGNzdHJpbmc+CiMgZGVmaW5lIERFQlVHIHByaW50Zgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgQnVkZ2V0LCBUb3RhbCwgRW50cnkgWzEwMF0sIEZ1biBbMTAwXSwgRFBUYWJsZSBbMTAxXVsyNTAxXSwgTWF4RnVuLCBNaW5FbnRyeSwgaSwgajsKaW50IG1haW4oKQp7CiAgIC8vZnJlb3BlbiAoIklucHV0LnR4dCIsICJyIiwgc3RkaW4pOwogICAvL2ZyZW9wZW4gKCJPdXRwdXQudHh0IiwidyIsIHN0ZG91dCk7CiAgIHNjYW5mICgiJWQlZCIsICZCdWRnZXQsICZUb3RhbCk7CiAgIHdoaWxlIChCdWRnZXQgJiYgVG90YWwpCiAgIHsKICAgICAgZm9yIChpID0gMDsgaSA8IFRvdGFsOyBpKyspIHNjYW5mICgiJWQlZCIsICZFbnRyeSBbaV0sICZGdW4gW2ldKTsKCiAgICAgIG1lbXNldCAoRFBUYWJsZSwgLTEsIHNpemVvZiBEUFRhYmxlKTsKICAgICAgZm9yIChpID0gMDsgaSA8PSBUb3RhbDsgaSsrKSBEUFRhYmxlIFtpXVswXSA9IDA7CiAgICAgIGZvciAoaSA9IDA7IGkgPD0gQnVkZ2V0O2krKykgRFBUYWJsZSBbMF1baV0gPSAwOwogICAgICBNYXhGdW4gPSAtMTsKCiAgICAgIGZvciAoaSA9IDE7IGkgPD0gVG90YWw7IGkrKykKICAgICAgICAgZm9yIChqID0gMTsgaiA8PSBCdWRnZXQ7IGorKykKICAgICAgICAgewogICAgICAgICAgICBEUFRhYmxlIFtpXVtqXSA9IERQVGFibGUgW2ktMV1bal07CiAgICAgICAgICAgIGlmIChqIC0gRW50cnkgW2ktMV0gPj0gMCAmJiBEUFRhYmxlIFtpLTFdW2otRW50cnlbaS0xXV0gIT0gLTEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgRFBUYWJsZSBbaV1bal0gPSBtYXggKERQVGFibGUgW2ktMV1bal0sIERQVGFibGUgW2ktMV1bai1FbnRyeVtpLTFdXSArIEZ1biBbaS0xXSk7CiAgICAgICAgICAgICAgIGlmIChEUFRhYmxlIFtpXVtqXSA+IE1heEZ1biB8fCAoRFBUYWJsZSBbaV1bal0gPT0gTWF4RnVuICYmIGogPCBNaW5FbnRyeSkpCiAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgTWF4RnVuID0gRFBUYWJsZSBbaV1bal07IE1pbkVudHJ5ID0gajsKICAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KICAgICAgICAgfQogICAgICBwcmludGYgKCIlZCAlZFxuIiwgTWluRW50cnksIE1heEZ1bik7CiAgICAgIHNjYW5mICgiJWQlZCIsICZCdWRnZXQsICZUb3RhbCk7CiAgIH0KICAgcmV0dXJuIDA7Cn0=