# 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=

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