#include <bits/stdc++.h>

using namespace std;
int k,m;
long long v[10001];
ifstream in("rucsac.in");
ofstream out("rucsac.out");
//#define in cin
//#define out cout
void rucs(int g, int p)
{
    for (int i=k;i>=0;i--)
    {
        if (v[i]!=-1)
        {
            if (v[i+g]<v[i]+g || v[i-g]+v[g]<v[i]+g)
            v[i+g]=p+v[i];
        }
    }
}

void cit()
{
    int n;
    int x,y;
    in>>n>>k;
    for (int i=1;i<=k;i++)
        v[i]=-1;
    for (int i=0;i<n;i++)
    {
        in>>x>>y;
        rucs(x,y);
    }
}

int checky()
{
    for (int i=1;i<=k;i++)
        if (v[i]>m)
        m=v[i];
    return m;
}

int main()
{
    cit();
    out<<checky();
    return 0;
}