#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]=b[i-1][j];
        	if(j-a[i].masa>=0)
        	{
        		b[i][j]=max(b[i-1][j],b[i-1][j-a[i].masa]+a[i].cost);
		    }
		}
	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;
    }
    int i=n;
    int j=g;
    while(i>-1)
    {
    	while(j>-1)
    	{
    		if(b[i][j]==(b[i-1][j-a[i].masa]+a[i].cost))
			{
			    //cout<<"Piatra "<<i<<" a fost luata"<<endl;
			    i--;
		    }
    		else
    		    j--;
		}
	}
    fout<<max1;
}