#include <bits/stdc++.h>

using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
const int NMAX=5005,GMAX=10005;
int n,g;
struct pereche
{
    int greutate,profit;
} v[NMAX];
int dp[GMAX];
int fin;
int main()
{
    in>>n>>g;
    for(int i=1; i<=n; i++)
    {
        in>>v[i].greutate>>v[i].profit;
    }
    for(int i=0; i<=g; i++)
        dp[i]=INT_MIN;
    dp[0]=0;
    for(int i=1; i<=n; i++)
        for(int j=g; j>=0; j--)
        {
            if(j>=v[i].greutate)
                dp[j]=max(dp[j],dp[j-v[i].greutate]+v[i].profit);
        }
    for(int i=0; i<=g; i++)
    {
        fin=max(fin,dp[i]);
    }
    out<<fin;
    return 0;
}