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


typedef struct
{
      int G;
      int V;

}obj;



void add_function(obj *object,int *N,int *G)
{
      int i,j;
      FILE *f;
      f=fopen("rucsac.in","r");
      if (f==NULL){
            printf("Error!");
            exit(0);
      }
      fscanf(f,"%d",N);
      fscanf(f,"%d",G);
      i=0;
      while(!feof(f))
             {
                  fscanf(f,"%d",&(object+i)->G);
                  fscanf(f,"%d",&(object+i)->V);
                  i++;
             } 
      
      
      
}



void knapsack(obj *object,int *N,int *G)
{
      int i,S=0,v[*N+2][*G+2],j;
      i=0;
      FILE *f;
      f=fopen("rucsac.out","w");
      for(i=0;i<=*N;i++)
            for (j=0;j<=*G;j++)
                  if(i==0 || j==0)
                        v[i][j]=0;
                  else
                        if((object+i)->G<=j){
                                    if ((object+i)->V+v[i-1][j-((object+i)->G)]>v[i-1][j])
                                          v[i][j]=(object+i)->V+v[i-1][j-((object+i)->G)];
                              else
                                      v[i][j]=v[i-1][j];
                        }
                  else
                        v[i][j]=v[i-1][j];
      
            i=*N;
            j=*G;
            while(i>0 && j>0){
                  if(v[i][j]==v[i-1][j])
                        i--;
                  else
                  {      
                        S=S+(object+i)->V;
                        j=j-(object+i)->G;
                        i--;
                  }
            }

      fprintf(f,"%d",S);
      fclose(f);
}



int main()
{
      int N, G, V;
      obj object[100];

      add_function(object,&N,&G);
      knapsack(object,&N,&G);

      

}