/* Olimpiadi di Informatica - Regionali 2008
 Soluzione per problema: MISSIONI
proposta prima:  Carlo Salvagno 2008 - Referente Regionale VEN1 - ITIS  "C. Zuccante"- Mestre (VE)

IDEA RISOLUTIVA - versione ricorsiva (inefficiente)

Si ricorre rispetto a due parametri : l'indice della missione e l'ultimo giorno impegnato. 
Dal main vengono chimati entrambi con il valore 0.

Il resto come commento al codice.
 
*/

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>

/* ------------------------------------------------------------------------- */
int maxMissioni(int* durata, int* termine, int prima, int ultima, int ultimoGiornoImpegnato) {
  int lCon, lSenza;
  if (prima > ultima) return 0; // zero missioni

  if (prima == ultima)     // una missione: o ci stiamo o non ci stiamo
         return  (ultimoGiornoImpegnato + durata[prima]) <= termine[prima] ? 1 : 0;

  if ( (ultimoGiornoImpegnato + durata[prima]) > termine[prima] )  // se siamo fuori con la prima missione
      return maxMissioni(durata, termine, prima+1, ultima, ultimoGiornoImpegnato); //passiamo alla successiva
  else {
	//calcoliamo  il massimo delle missioni includendo la prima missione ed escludendola
    lCon = maxMissioni(durata, termine, prima+1, ultima, durata[prima] + ultimoGiornoImpegnato);
    lSenza = maxMissioni(durata, termine, prima+1, ultima, ultimoGiornoImpegnato);
    // se includendola non ci perdiamo la teniamo 
    if (lCon  >= lSenza) return 1 + lCon;
    else return lSenza;
  }
}
/* ------------------------------------------------------------------------- */


int main(int argc, char *argv[]) {
  ifstream in("input.txt");
  ofstream out("output.txt");
  int ultimo, i, max;
  int *durata, *termine;
  int n;


  /* -- Lettura input -- */
  in >> n;

  durata = new int[n];
  termine = new int[n];

  // lettura durate e scadenze 
  for ( i = 0 ; i < n ; i++ )  {
    in >> durata[i] >> termine[i] ;
  }

  max = maxMissioni(durata, termine, 0, n-1, 0);
 // cout <<max <<"\n";
  out <<max <<"\n";
  out.close();
  in.close();

 // system("PAUSE");
  return 0;
}