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

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

// Problema rucsacului 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[2][g + 1]; // vectorul de DP pt greutati
  for ( uint16_t i = 0; i <= g; i++ )
    dp[0][i] = 0;

  /*
  for ( uint16_t i = 0; i <= g; i++ )
    {
      printf ( "%2hu ", i );
    }
  printf ( "\n" );
  for ( uint16_t i = 0; i <= g; i++ )
    {
      printf ( "%2lu ", dp[i] );
    }
  printf ( "\n\n" );
  */

  for ( uint16_t j = 0; j < n; j++ )
    {
      for ( int16_t i = g; i >= 0; i-- ) // daca e tot uint, risc overflow
	{
	  if ( dp[j % 2][i] < dp[j % 2][i - arr[j].w] + arr[j].p )
	    {
	      dp[(j + 1) % 2][i] = dp[j%2][i - arr[j].w] + arr[j].p;
	    }
	}
    }

  /*
  for ( uint16_t i = 0; i <= g; i++ )
    {
      printf ( "%2hu ", i );
    }
  printf ( "\n" );
  for ( uint16_t i = 0; i <= g; i++ )
    {
      printf ( "%2lu ", dp[i] );
    }
  */

  rez = dp[(n - 1) % 2][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;
}


// FAIL

// da rezultat gresit, dar aproximativ. In schimb, cel putin pe teste, este foarte rapid

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

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

// Problema rucsacului de pe infoarena

// Prima incercare: ordonez obiectele dupa eficienta ( p / w ) si le adaug apoi

typedef struct
{
  uint16_t w, p;
} ITEM;

int ordine ( const void *e1, const void *e2 )
{
  ITEM *i1 = ( ITEM * ) e1;
  ITEM *i2 = ( ITEM * ) e2;
  double r1 = i1->p / ( double ) i1->w, r2 = i2->p / ( double ) i2->w; // rapoartele de eficienta
  if ( r1 != r2 )
    {
      if ( r1 < r2 )
	return 1;
      return -1;
    }
  return i2->w - i1->w;
}

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

  for ( uint16_t i = 0; i < n; i++ )
    {
      if ( act_g + arr[i].w <= g )
	{
	  rez += arr[i].p;
	  act_g += arr[i].w;
	  printf ( "Am selectat elem || %hu | %hu\n", arr[i].w, arr[i].p );
	}
    }
  
  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;
}
 */