#include <stdio.h>

using namespace std;
int n, g, d[2][10000];
int w[5000], p[5000];
int max(int a, int b)
{
    if(a<=b) return b;
    return a;
}
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d %d", &n, &g);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d", &w[i], &p[i]);
    }
    for(int greutate=0; greutate<=g; greutate++)
        if(greutate<w[0])
            d[0][greutate]=0;
        else
            d[0][greutate]=p[0];
    for(int i=1; i<n; i++)
        for(int greutate=0; greutate<=g; greutate++)
            {
                d[i%2][greutate]=d[(i-1)%2][greutate];
                if(w[i]<=greutate)
                    d[i%2][greutate]=max(d[(i-1)%2][greutate-w[i]]+p[i],d[(i-1)%2][greutate]);
            }
    printf("%d ", d[(n-1)%2][g]);
    return 0;
}