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

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

int n,g,dp[2][10005],cost[5005],greutate[5005];

void Citire()
{
    int i,j;
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>greutate[i]>>cost[i];
    fin.close();
    for(i=0;i<=1;i++)
        for(j=0;j<=g;j++)
            dp[i][j]=-infinit;
    dp[0][0]=0;
}

void Rezolvare()
{
    int i,j,l1,l2;
    for(i=1;i<=n;i++)
    {
        l1=(i&1);l2=((i-1)&1);
        for(j=0;j<=g;j++) dp[l1][j]=-infinit;
        for(j=0;j<=g;j++)
        {
            if(greutate[i]<=j)
                dp[l1][j]=dp[l2][j-greutate[i]]+cost[i];
            dp[l1][j]=max(dp[l1][j],dp[l2][j]);
        }
    }
    int mx=0;
    for(i=1;i<=g;i++)
        mx=max(mx,dp[l1][i]);
    fout<<mx<<"\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}