// Programmation dynamique.
// Problème du sac à dos
// AVEC RÉPÉTITION
#include <stdio.h>
#include <stdlib.h>

typedef struct _t_paire { int weight, value; } t_paire;

int cmp(const void *n1, const void *n2)
{
  return *(int *)n1 - *(int *)n2;
} // cmp()

int main()
{
  int poids, nobjs, i, j, x, y, cpt;
  t_paire *objet;
  int *memo;
  int *liste;

  scanf("%d\n", &poids);
  scanf("%d\n", &nobjs);

  objet = (t_paire *)malloc(nobjs*sizeof(t_paire));

  for(i = 0; i < nobjs; i++)
    scanf("%d %d\n", &objet[i].weight, &objet[i].value);

  memo = (int *)malloc((poids+1)*sizeof(int));

  memo[0] = 0;
  for(int w = 1; w <= poids; w++)
    memo[w] = -1;

  for(int w = 1; w <= poids; w++)
  {
    for(i = 0; i < nobjs; i++)
    {
      if(objet[i].weight <= w)
      {
        if(memo[w-objet[i].weight] + objet[i].value > memo[w])
          memo[w] = memo[w-objet[i].weight] + objet[i].value;
      }
    }
  }

  // Valeur optimale
  printf("%d\n", memo[poids]);

  // Désallocations
  free(objet); objet = NULL;
  free(memo); memo = NULL;

  return 0;
} // main()