#include <iostream>
#include <fstream>

using namespace std;

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

int n,G,dp[10005];

struct gp {
    int g, p;
} a[5001];

void citire()
{
    fin>>n>>G;
    for(int i=0;i<n;i++)
        fin>>a[i].g>>a[i].p;
}

int profmax()
{
    for(int i=1;i<a[0].g;i++)
        dp[i]=0;
    for(int i=a[0].g;i<=G;i++)
        dp[i]=a[0].p;
    for(int i=1;i<n;i++)
        for(int j=G;j>=a[i].g;j--)
    {
        dp[j]=max(dp[j],dp[j-a[i].g]+a[i].p);
    }
    return dp[G];
}

int main()
{
    citire();
    fout<<profmax();
    return 0;
}