#include <stdio.h>

#define MAX_DULJINA 1000

int duljina_puta,broj_voznji;

long nova_cijena;
long polje_min[MAX_DULJINA + 1],polje_max[MAX_DULJINA + 1];

struct {
         int koliko,cijena;
       } voznja[MAX_DULJINA];

void ucitaj_podatke(void)
{
  int i;
  FILE *fp;

  fp = fopen("TAXI.IN","rt");

  fscanf(fp,"%d%d",&duljina_puta,&broj_voznji);

  for (i = 0;i < broj_voznji;++i)
    fscanf(fp,"%d%d",&voznja[i].koliko,&voznja[i].cijena);

  fclose(fp);
}

void rijesi(void)
{
  int i,j;

  for (i = 1;i <= duljina_puta;++i)
  {
    polje_min[i] = polje_max[i] = 0l;

    for (j = 0;j < broj_voznji;++j)
      if (voznja[j].koliko == i)
      {
        polje_min[i] = polje_max[i] = voznja[j].cijena;
        break;
      }

    for (j = 0;j < broj_voznji;++j)
      if (i - voznja[j].koliko >= 1)
      {
        if (polje_min[i - voznja[j].koliko])
        {
          nova_cijena = polje_min[i - voznja[j].koliko] + voznja[j].cijena;

          if (!polje_min[i] || nova_cijena < polje_min[i])
            polje_min[i] = nova_cijena;
        }

        if (polje_max[i - voznja[j].koliko])
        {
          nova_cijena = polje_max[i - voznja[j].koliko] + voznja[j].cijena;

          if (nova_cijena > polje_max[i])
            polje_max[i] = nova_cijena;
        }
      }
  }
}

void zapisi_rjesenje(void)
{
  FILE *fp;

  fp = fopen("TAXI.OUT","wt");

  if (polje_min[duljina_puta])
    fprintf(fp,"%ld\n%ld\n",polje_min[duljina_puta],polje_max[duljina_puta]);
  else
    fprintf(fp,"-1\n");

  fclose(fp);
}

int main(void)
{
  ucitaj_podatke();
  rijesi();
  zapisi_rjesenje();

  return 0;
}