#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int Nmax=5e3+5;
int a[Nmax][Nmax];
int main()
{
    int n,G,x,value;
    f>>n>>G;
    for(int i=1; i<=n; i++)
    {
        f>>x>>value;
        for(int j=1;j<=G;j++){

            if(j>=x)
            {
                if(a[i-1][j]>a[i-1][j-x]+value)
                    a[i][j]=a[i-1][j]
                else
                    a[i][j]=a[i-1][j-x]+value;
            }
            else
                a[i][j]=a[i-1][j];

        }
    }

        g<<a[n][G];

    return 0;
}