#include <fstream>
#include <algorithm>

using namespace std;

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

int dp[10005],gr[5005],profit[5005];

int main()
{
    int n,G;
    in>>n>>G;
    for(int i=1;i<=n;i++)
    {
        in>>gr[i]>>profit[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int g=G;g>=0;g--)
        {
            if(gr[i]<=g)
            {
                if(g-gr[i]==0 || dp[g-gr[i]]!=0)
                {
                    dp[g]=max((profit[i]+dp[g-gr[i]]),dp[g]);
                }
            }
        }
    }
    int rasp=0;
    for(int i=0;i<=G;i++)
    {
        rasp=max(rasp,dp[i]);
    }
    out<<rasp;
    return 0;
}