#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,dp[5005][10005],m;
struct Dublu
{
    int greutate,profit;
};
Dublu t[5005];
void Citire()
{
    int i,j,sol;
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>t[i].greutate>>t[i].profit;
    int lin = 1;
    for(i=1;i<=n;i++, lin = 1 - lin)
        for(j=0;j<=g;j++)
        {
            dp[lin][j]=dp[1 - lin][j];
            if(j-t[i].greutate >= 0)
                dp[lin][j]=max(dp[lin][j],dp[1 - lin][j-t[i].greutate]+t[i].profit);
        }
    sol=0;
    for(i=1;i<=g;i++) if(dp[1 - lin][i]>sol) sol=dp[1 - lin][i];
    fout<<sol<<"\n";
}
int main()
{
    Citire();
    return 0;
}