#include <fstream>


#define nMax 5001
#define gMax 10001
#define INF 2000000000
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g, Sol;
int dp[gMax];
struct car
{
    int weight;
    int price;
}v[nMax];
int main()
{
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>v[i].weight>>v[i].price;
    for(int i=g; i>=1; i--)
        dp[i]=-INF;
    for(int i=1; i<=n; i++)
    {
        for(int j=g-v[i].weight; j>=0; j--)
            if(dp[j]!=-INF && dp[j]+v[i].price>dp[j+v[i].weight])
        {
            dp[j+v[i].weight]=dp[j]+v[i].price;
            Sol=max(Sol, dp[j+v[i].weight]);
        }
    }

    fout<<Sol;
}