#include<bits/stdc++.h>
using namespace std;


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


int greutate[5000],profit[5000],n;
int dp[5001];
int capacitate;

void read()
{
    in>>n>>capacitate;

    for(int i=0; i<n; i++)
        in>>greutate[i]>>profit[i];
}
int dpp()
{
    for(int i=1; i<=capacitate; i++)
    {
        dp[i]=-1;
    }


    for(int i=0; i<n; i++)
    {
        for(int k=capacitate-greutate[i]; k>=0; k--)
        {
            if(dp[k]!=-1 && profit[i]+dp[k]>dp[k+greutate[i]])
            {
                dp[k+greutate[i]]=profit[i]+dp[k];
            }

        }
    }

    return dp[capacitate];
}



int main()
{
    read();
    out<<dpp();


}