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

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

int n,g,dp[5005][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<=n;i++)
        for(j=0;j<=g;j++)
            dp[i][j]=-infinit;
    dp[0][0]=0;
}

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

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