#include <bits/stdc++.h>
using namespace std;
int main(){
 
ifstream f("rucsac.in");
ofstream g("rucsac.out");
	
	int n,W;
	int v[100],w[100],i,j; int m[100];
	f>>n>>W;
	for (int i=0;i<n;i++)	
	f>>v[i]>>w[i];
	for (j= 0 ;j< W;j++)
    m[0, j] = 0;
  
 for (i=1;i<n;i++)
     for (j= 0;j<W;j++)
         if (w[i] > j)
             m[i, j] = m[i-1, j];
	    m[i, j] = max(m[i-1, j], m[i-1, j-w[i]] + v[i]);
g<<m[n,W];

return 0;

	
}