#include <iostream>
#include <fstream>

using namespace std;

int w[5005],p[5005],n,g,a[5005];

void citire()
{
    ifstream fin("rucsac.in");
    fin>>n>>g;
    for(int i=1;i<=n;i++)
        fin>>w[i]>>p[i];
}

int maxim(int x,int y)
{
    if(x>y)
        return x;
    return y;
}

int fct()
{
    for(int i=w[1];i<=g;i++)
        a[i]=p[1];
    for(int i=2;i<=n;i++)
        for(int j=g;j>0;j--)
            a[j]=maxim(a[j],p[i]+a[j-w[i]]);
    return a[g];
}

int main()
{
    citire();
    ofstream fout("rucsac.out");
    fout<<fct();
    return 0;
}