#include <iostream>
#include <stdio.h>

#define nn 5010
#define mm 10010

using namespace std;

int n,cap, g[nn], c[nn], a[2][mm];

void citire()
{
    freopen ("rucsac.in","r",stdin);

    scanf("%d %d", &n, &cap);
    for(int i=1;i<=n;++i)
        scanf("%d %d", &g[i], &c[i]);
}

int f(int x)
{
    if(x==1) return 0;
    return 1;
}

void solve()
{
    freopen ("rucsac.out","w",stdout);
    int L=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=cap;++j)
        {
            a[f(L)][j] = a[L][j];
            if(g[i] <= j)
                a[f(L)][j] = max(a[f(L)][j], a[L][j-g[i]] + c[i]);
        }
        L=f(L);
    }
    printf("%d", a[L][cap]);
}


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