#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max(a,b) \
   ({ __typeof__ (a) _a = (a); \
       __typeof__ (b) _b = (b); \
     _a > _b ? _a : _b; })
struct Generator
{
	int greutate;
	int profit;

};
int a[1001]={0};
struct Generator G_list[1001];
int results[1001][5001]={0,0};
//int w[5001]={0},p[5001]={0};
/*void sort(int size)
{
struct    Generator temp;
    int i,j;
for(i=0;i<size-1;i++)
for(j=0;j<size-1-i;j++)
if(G_list[j].coef<G_list[j+1].coef)
{
    temp=G_list[j];
    G_list[j]=G_list[j+1];
    G_list[j+1]=temp;
}
}*/
int main()
{
    float e_actuala,e_maxima=0,c_actual,e_total=0;
    bool flag=false;
    int g,i,j,w;

     FILE *fp;

      fp = fopen("energii.in", "r");
      fscanf(fp,"%d %d",&g,&w);


      for(int i=1;i<=g;i++)
      {

         fscanf(fp,"%d %d",&G_list[i].greutate,&G_list[i].profit);
       //  G_list[i].coef=G_list[i].energie / G_list[i].cost;
         //e_total+=G_list[i].energie;
      }

  /* sort(g);
i=0;

   while(e_actuala<e_maxima && i<g)
   {
       for(j=i;j<g;j++)
        if(e_actuala+G_list[j].energie>=e_maxima)
        {

            e_actuala+=G_list[i].energie;
            c_actual+=G_list[i].cost;
            flag=true;
            break;
       }
      if(flag==false)
      {

            e_actuala+=G_list[i].energie;
            c_actual+=G_list[i].cost;
      }

       i++;
   }
   if(e_total<e_maxima) c_actual=-1;*/
    fclose(fp);
        fp = fopen("energii.out", "w");
      fprintf(fp,"%d",rucsac(g,w));
fclose(fp);
    return 0;
}
int rucsac(int n,int W){
   for (int cap = 0; cap <= W; ++cap) {
        results[0][cap] = 0;
    }

    // cazul general
    for (int i = 1; i <= n; ++i) {
        for (int cap = 0; cap <= W; ++cap) {
            // nu folosesc obiectu i => e solutia de la pasul i - 1
            results[i][cap] = results[i-1][cap];

            // folosesc obiectul i, deci trebuie sa rezerv w[i] unitati in rucsac
            // inseamna ca inainte trebuie sa ocup maxim cap - w[i] unitati
            if (cap - G_list[i].greutate >= 0) {
                int sol_aux = results[i-1][cap - G_list[i].greutate] + G_list[i].profit;

                results[i][cap] = max(results[i][cap], sol_aux);
            }
        }
    }

    return results[n][W];
}