// g++ knapsack_selection.cpp
#include <cstdio>
#include <cstring>
#include <algorithm>

// currentVolume: Das restliche (freie) Volumen im Rucksack
// i: Aktueller Gegenstand
// Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand
int knapsack( const int currentVolume, const int i );

// Maximale Anazahl an Gegenständen
const int maxN = 10;
// Maximales Volumen des Rucksacks
const int maxV = 30;
// Anzahl an Byte für unseren Dynamisierungs-Array
const int resultLength = ( maxV + 1 ) * sizeof( int );

// Volumen des Rucksacks
int V;
// Anzahl an Gegenständen
int n;
// Volumen der einzelnen Gegenstände
int v[maxN];
// Werte der einzelnen Gegenstände
int w[maxN];
// Gespeicherte Ergebnisse von bisherigen Berechnungen
int results[maxN][maxV + 1];

int main()
{
  // Eingabe der Daten
  scanf( "%d %d", &V, &n );
  for( int i = 0; i < n; i++ )
    scanf( "%d %d", &( v[i] ), &( w[i] ) );
  // Initialisierung der Dynamisierungs-Matrix mit -1
  for( int i = 0; i < n; i++ )
    memset( results[i], -1, resultLength );
  // Berechnung des optimalen Wertes
  int r = knapsack( V, 0 );
  // Belegtes Volumen beim optimalen Ergebnis suchen.
  // Das optimale Ergebnis befindet sich immer in der ersten Spalte!
  int currentVolume = -1;
  for( int i = 0; i <= maxV && currentVolume == -1; i++ )
  {
    if( results[0][i] == r )
      currentVolume = i;
  }
  // Über alle Gegenstände iterieren (-1, weil mit i+1 gerechnet wird)
  for( int i = 0; i < n - 1; i++ )
  {
    // Zuerst prüfen ob der aktuelle Gegenstand überhaupt in den Rucksack passt, dann
    // versuchen den aktuellen Gegenstand aus dem Rucksack zu nehmen.
    // Stimmt der Wert an der neuen Position?
    // aktueller Wert im Rucksack - Wert des aktuellen Gegenstands 
    //       == Maximum für diesen Gegenstand mit dem neuen Volumen
    if( currentVolume - v[i] >= 0 
        && r - w[i] == results[i + 1][currentVolume - v[i]] )
    {
      // Gegenstand war im Rucksack
      printf( "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
      // Restlichen Wert im Rucksack anpassen
      r -= w[i];
      // Restliches Volumen der Gegenstände im Rucksack anpassen
      currentVolume -= v[i];
    }
    else
    {
      // Gegenstand war nicht im Rucksack
      printf( "NOT selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
    }
  }
  // Der letzte Gegenstand muss speziell geprüft werden, da der Index
  // i + 1 dann nicht mehr vorhanden ist.
  // Ist jetzt noch etwas im Rucksack, muss es der letzte Gegenstand sein.
  // r entspricht damit auch dem Wert des letzten Gegenstandes
  if( r > 0 )
    printf( "selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );
  else
    printf( "NOT selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] );
  return 0;
}


int knapsack( const int currentVolume, const int i )
{
  if( i < n )
  {
    if( results[i][currentVolume] != -1 )
      return results[i][currentVolume];
    return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ),
                                                 ( currentVolume - v[i] >= 0 )
                                                 ? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) ) 
                                                 : 0 );
  }
  return 0;
}