#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G,a[3][10005];
pair <int,int> v[5005];
int main()
{
    f>>n>>G;
    for(int i=1; i<=n; i++)
        f>>v[i].first>>v[i].second;
    for(int i=1,k=1; i<=n; i++,k++)
    {
        for(int j=1; j<=G; j++)
        {
            if(v[i].first<=j)
                a[k][j]=max(a[k-1][j],a[k-1][j-v[i].first]+v[i].second);
            else
                a[k][j]=a[k-1][j];
        }
        if(k==2)
            {
                for(int j=1; j<=G; j++)
                    a[k-1][j]=a[k][j];
                k--;
            }
    }
    g<<a[2][G];
    return 0;
}