// Programmation dynamique.
// Problème du sac à dos sans 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 **matrice;
  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);

  matrice = (int **)malloc(nobjs*sizeof(int *));
  for(i = 0; i < nobjs; i++)
    matrice[i] = (int *)malloc((poids+1)*sizeof(int));

  // 1ère ligne
  for(j = 0; j <= poids; j++)
    if(objet[0].weight > j)
      matrice[0][j] = 0;
    else
      matrice[0][j] = objet[0].value;

  // Autres lignes
  for(i = 1; i < nobjs; i++)
  {
    for(j = 0; j <= poids; j++)
    {
      if(objet[i].weight > j)
        matrice[i][j] = matrice[i-1][j];
      else
      {
        x = matrice[i-1][j];
        y = matrice[i-1][j-objet[i].weight] + objet[i].value;
        matrice[i][j] = (x>y) ? x : y;
      }
    }
  }

  // Valeur optimale
  printf("%d\n", matrice[nobjs-1][poids]);

  // Récupérer les objets à mettre dans le sac
  liste = (int *)malloc(nobjs*sizeof(int));
  for(i = 0; i < nobjs; i++)
    liste[i] = nobjs+1;
  cpt = 0;

  i = nobjs-1;
  j = poids;
  while(matrice[i][j] == matrice[i][j-1])
    j--;

  while(j >= 0)
  {
    while(i > 0 && matrice[i][j] == matrice[i-1][j])
      i--;
    j -= objet[i].weight;
    if(j >= 0)
    {
      liste[cpt++] = i+1;
      //printf("Objet %d\n", i+1);
    }
    i--;
  }

  qsort(liste, cpt, sizeof(int), cmp);
  for(i = 0; i < cpt; i++)
    printf("%d ", liste[i]);
  printf("\b\n");
  
  // Désallocations
  free(objet); objet = NULL;
  for(i = 0; i < nobjs; i++) { free(matrice[i]); matrice[i] = NULL; }
  free(matrice); matrice = NULL;
  free(liste); liste = NULL;

  return 0;
} // main()