#include <stdio.h>
#define N 5000
#define G 10000
#define max(a, b) ((a) > (b) ? (a) : (b))
int m[2][G];
int w[N],p[N];

int main()
{
    int n,kg,rand = 1;
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&kg);
    for(int i = 1; i <= n; i++)
        scanf("%d %d",&w[i],&p[i]);
    for(int i = 1; i <= n; i++,rand = 1 - rand)
        for(int j = 0; j <= kg; j++)
            if(j >= w[i])
                m[rand][j] = max(m[1 - rand][j],m[1 - rand][j - w[i]] + p[i]);
            else
                m[rand][j] = m[1 - rand][j];

    printf("%d\n",m[rand][kg]);
    return 0;
}