# include <cstdio>
using namespace std;

FILE *f = freopen("rucsac.in", "r", stdin);
FILE *g = freopen("rucsac.out", "w", stdout);

const int N_MAX = 30001;
const int G_MAX = 10001;
const int bufferDIM = 10001;

class inputReader{
    int pos;
    char buffer[bufferDIM];

public :

    bool digit(char c)
    {
        return ('0' <= c && c <= '9');
    }

    void get_buffer()
    {
        fread(buffer, 1, bufferDIM, stdin);
        pos = 0;
    }

    void getINT(int &nr)
    {
        while (!digit(buffer[pos]))
            if (++pos == bufferDIM)
                get_buffer();

        nr = 0;

        while (digit(buffer[pos]))
        {
            nr = nr * 10 + buffer[pos] - '0';

            if (++pos == bufferDIM)
                get_buffer();
        }
    }
}cin;

int w[N_MAX];
int p[N_MAX];
int dp[2][G_MAX];

int n, G;

void read()
{
    cin.getINT(n);
    cin.getINT(G);

    for (int i=1; i<=n; i++)
    {
        cin.getINT(w[i]);
        cin.getINT(p[i]);
    }
}

void solve()
{
    int l = 1;

    for (int i=1; i<=n; i++)
    {
        l = 1 - l;

        for (int greutate=0; greutate<=G; greutate++)
        {
            dp[1-l][greutate] = dp[l][greutate];

            if (greutate >= w[i])
                if (dp[l][greutate - w[i]] + p[i]> dp[1-l][greutate])
                    dp[1-l][greutate] = dp[l][greutate - w[i]] + p[i];
        }
    }

    printf("%d\n", dp[1-l][G]);
}

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