#include<bits/stdc++.h>
using namespace std;
struct rucsac
	{
		int cost,masa;
	};
int max(int a,int b)
{
	if(a>b)return(a);else return(b);
}
int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n,g;
	fin>>n>>g;
	rucsac a[n+1];
	for(int i=1;i<n+1;i++)
    	fin>>a[i].masa>>a[i].cost;
    int b[n+1][g+1];
    for(int i=0;i<g+1;i++)
        for(int j=0;j<g+1;j++)
        {
            b[0][j]=0;
            b[i][0]=0;
        }
    for(int i=1;i<n+1;i++)
        for(int j=1;j<g+1;j++)
        {
        	if(j-a[i].masa<0)b[i][j]=0;
        	if(j-a[i].masa>=0)
        	{
        		if(i==1)b[i][j]=a[i].masa;else{
        		b[i][j]=max(b[i-1][j],b[i-1][j-a[i].masa]+a[i].cost);
        		//if(b[i][j]==(b[i-1][j-a[i].masa]+a[i].cost))cout<<"Piatra "<<i-1<<" a fost luata"<<endl;
		    }
		    }
		}
	int max1=-1;
	for(int i=0;i<n+1;i++)
	{
	    for(int j=0;j<g+1;j++)
	    {
	        if(max1<b[i][j])max1=b[i][j];
	       // cout<<b[i][j]<<" ";
	    }
	    //cout<<endl;
    }
    fout<<max1;
}