#include <cstdio>
#define LMAX 10005
#define NMAX 5005
#define MAX(a,b) a>b?a:b
using namespace std;
FILE *fin=fopen("rucsac.in", "r");
FILE *fout=fopen("rucsac.out", "w");

struct obiect{
    int g, v;
};
obiect ob[NMAX];

int n, g;
int now, last;
int dp[2][LMAX];

int main()
{
    fscanf(fin, "%d %d",&n, &g);
    for (int i=1;i<=n;i++)
    {
        fscanf(fin, "%d %d",&ob[i].g, &ob[i].v);
    }
    now = 1, last = 0;
    for (int i = 1;i<=n;i++)
    {
        for (int j=1;j<=g;j++)
        {
            dp[now][j] = dp[last][j];
            if (ob[i].g > j)
            {
                continue;
            }
            int v2 = dp[last][j-ob[i].g]+ob[i].v;
            dp[now][j] = MAX(v2, dp[now][j]);
        }
        now = 1-now;
        last = 1-last;
    }
    fprintf(fout, "%d\n", dp[last][g]);
    return 0;
}