#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define FILE_IN "rucsac.in"
#define FILE_OUT "rucsac.out"

// Problema rucsacului 1 / 0 de pe infoarena

// A doua incercare: merg dupa indicatii

typedef struct
{
  uint16_t w, p;
} ITEM;

int ordine ( const void *e1, const void *e2 )
{
  ITEM *i1 = ( ITEM * ) e1;
  ITEM *i2 = ( ITEM * ) e2;
  if ( i2->w != i1->w )
    return i2->w - i1->w;
  return i2->p - i1->p;
}

uint64_t rezolvare ( uint16_t n, uint16_t g, ITEM *arr )
{
  uint64_t rez = 0;

  uint64_t dp[g + 1]; // vectorul de DP pt greutati
  for ( uint16_t i = 0; i <= g; i++ )
    dp[i] = 0;

  for (uint16_t j = 0; j < n; j++)
    {
    for (int16_t i = g; i >= arr[j].w; i--)
      { // Iterăm în sens invers și verificăm să nu depășim indexul
	if (dp[i] < dp[i - arr[j].w] + arr[j].p) {
	  dp[i] = dp[i - arr[j].w] + arr[j].p;
	}
      }
    }

  rez = dp[g];
  
  return rez;
}

int main ( void )
{
  FILE *fin, *fout;
  fin = fopen ( FILE_IN, "r" ); fout = fopen ( FILE_OUT, "w" );

  if ( fin == NULL || fout == NULL )
    {
      perror ( "Eroare la deschidere fisiere\n" );
      exit ( -1 );
    }

  
  uint16_t n, g;
  fscanf ( fin, "%hu %hu", &n, &g );

  ITEM arr[n];

  for ( uint16_t i = 0; i < n; i++ )
    {
      fscanf ( fin, "%hu %hu\n", &arr[i].w, &arr[i].p );
      if ( arr[i].w > g )
	{
	  i--, n--;
	  // printf ( "Un element > G\n" );
	}
    }

  qsort ( arr, n, sizeof ( ITEM ), ordine ); // preordonarea

  uint64_t rez = rezolvare ( n, g, arr ); // rezolvarea propriu-zisa

  fprintf ( fout, "%lu\n", rez );
  // printf ( "%lu\n", rez );


  /*
  for ( uint16_t i = 0; i < n; i++ )
    {
      printf ( "%2hu %2hu || %2lf\n", arr[i].w, arr[i].p, arr[i].p / ( double ) arr[i].w );
    }
  */
  

  
  if ( ( fclose ( fin ) ) != 0 || ( fclose ( fout ) ) != 0 )
    {
      perror ( "Eroare la inchidere fisiere\n" );
      exit ( -2 );
    }
  
  return 0;
}