//Metoda imcompleta!!!!!

//knapsack problem
#include <iostream>
#include <fstream>
using namespace std;
//function for defining the maximum from 2 numbers;
int max (int a, int b){
	return (a>b)?a:b;
}

int knapsack(int W, int wt[], int n, int val[])
{
   int i, w;
   int K[n+1][W+1];
 
   // Build table K[][] in bottom up manner
   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];
}

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int main(){	
	int W,n;
	fin>>n>>W;
	int val[n];
	int wt[n];
	
	for (int i=0; i<n; i++){
	fin>>wt[i]>>val[i];
	}
	fout<<knapsack (W, wt, n, val);
	fin.close();
	fout.close();
	return 0;
}