#include<bits/stdc++.h>

using namespace std;

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

int n,G,W[10002], P[10002],i,j, B[10002][10002];
int main(){
	fin>>n>>G;
	for (i=1; i<=n; i++)
	   fin>>W[i]>>P[i];
	for (i=1; i<=n; i++)
      for(j=1; j<=G; j++)
      {
      	B[i][j]=B[i-1][j];
      	if (W[i]<=j)
      	 B[i][j] = max(B[i-1][j], B[i - 1][j - W[i]] + P[i]);
	  }	
fout<<B[n][G];
   
}