#include <iostream>
#include <stdio.h>
#define NMAX 5001
#define C 10001
using namespace std;

int n,c,p[NMAX],g[NMAX],cost[NMAX][C];

void citire()
{
    freopen ("rucsac.in","r",stdin);
    scanf ("%d%d",&n,&c);
    for (int i=0;i<n;i++)
        scanf ("%d%d",&g[i],&p[i]);
}

int main()
{
    citire();
    for (int j=1;j<=c;j++)
        if (g[0]==j)
            cost[0][j]=p[0];
    for (int i=1;i<n;i++)
        for (int j=1;j<=c;j++)
        {
            cost[i][j]=cost[i-1][j];

            if (g[i]==j && g[i]<=c && cost[i][j]<p[i])
                cost[i][j]=p[i];

            int s=cost[i-1][j-g[i]]+p[i];
            if (g[i]<j && cost[i][j]<s)
                cost[i][j]=s;
        }
    freopen ("rucsac.out","w",stdout);
    printf("%d",cost[n-1][c]);
    return 0;
}