#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;
    for(i=1;i<=n;i++)
        for(j=0;j<=g;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j-t[i].greutate >= 0)
                dp[i][j]=max(dp[i][j],dp[i-1][j-t[i].greutate]+t[i].profit);
        }
    sol=0;
    for(i=1;i<=g;i++) if(dp[n][i]>sol) sol=dp[n][i];
    fout<<sol<<"\n";
}
int main()
{
    Citire();
    return 0;
}