#include<iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int knapSack(int W,int wt[],int val[],int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i=0;i<=n;i++)
   {
       for(w=0;w<=W;w++)
       {
           if(i==0 || w==0)K[i][w]=0;
           else if(wt[i-1]<=w)K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
           else K[i][w]=K[i-1][w];
       }
   }
   return K[n][W];
}
int main()
{
    int val[100],wt[100],w,n,i;
    fin>>n>>w;
    for(i=0;i<n;i++)fin>>wt[i]>>val[i];
    fout<<knapSack(w,wt,val,n);
    return 0;
}