#include <bits/stdc++.h>
#define DIM 5001

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, G;
int C[DIM][2*DIM], gr[DIM], c[DIM];

void read()
{
    f>>n>>G;
    for (int i=1; i<=n; i++)
        f>>gr[i]>>c[i];
    f.close();
}

void solve()
{
    for (int i=1; i<=n; i++)
        for (int j=1; j<=G; j++)
            if (gr[i]<=j)
                if (C[i-1][j]<C[i-1][j-gr[i]]+c[i])
                    C[i][j]=C[i-1][j-gr[i]]+c[i];
                else
                    C[i][j]=C[i-1][j];
            else
                    C[i][j]=C[i-1][j];
}

void write()
{
    g<<C[n][G]<<'\n';
    g.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}