#include <bits/stdc++.h>

using namespace std;

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

int n,g,dp[10005];
struct obiect{
    int w,p;
}v[5005];
void citire()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].w>>v[i].p;
    }
}

void rucsac()
{
    int sol=0;
    for(int i=1;i<=n;i++)
    for(int j=g-v[i].w;j>=0;j--){
        if(dp[j+v[i].w]<dp[j]+v[i].p)
        {
            dp[j+v[i].w]=dp[j]+v[i].p;
            if(dp[j+v[i].w]>sol)
                sol=dp[j+v[i].w];
        }
    }
    fout<<sol;
}

int main()
{
    citire();
    rucsac();
    return 0;
}