// g++ knapsack_dynamic.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 = 300;
// Maximales Volumen des Rucksacks
const int maxV = 1000;
// 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 und Ausgabe
  printf( "%d\n", knapsack( V, 0 ) );
  return 0;
}


int knapsack( const int currentVolume, const int i )
{
  // Prüfen, ob ein gültiger Index übergeben wurde
  if( i < n )
  {
    // Prüfen, ob der Wert bereits berechnet wurde.
    if( results[i][currentVolume] != -1 )
      return results[i][currentVolume];
    // Berechne Wert ohne den aktuellen Gegenstand
    int a = knapsack( currentVolume, i + 1 );
    // Berechne Wert mit dem aktuellen Gegenstand, wenn noch Platz dafür ist
    int b = 0;
    if( currentVolume - v[i] >= 0 )
      b = w[i] + knapsack( currentVolume - v[i], i + 1 );
    // Maximum der Berechnung wird gespeichert und zurückgegeben
    results[i][currentVolume] = std::max( a, b );
    return results[i][currentVolume];
  }
  return 0;
}