#include<fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");


/*Problema se rezolva folosind metoda programarii dinamice,
iar pentru a ne incadra in limita de memorie este necesar sa
observam faptul ca putem retine doar ultimele doua randuri din matrice
sub forma unui vector,ceea ce reduce complexitatea de memorie de la
O(n*g) la O(g),,unde n e numarul de fete si g e numarul de swipeuri disponibile.*/


int dp[10001];
int p[5001],c[5001];




int main()
{
    int fete,s;
    cin>>fete>>s;

    for(int i=1;i<=fete;i++)
        {
            cin>>c[i]>>p[i];
        }

    //dinamica

    for(int i=1;i<=fete;i++)
        {
            for(int j=s;j>=0;j--)
                {
                    if(j>=c[i])
                        dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
                }
        }
    cout<<dp[s]<<endl;
    return 0;//superpeace

}