#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct obiect
{
    int p,w;
};

obiect v[5001];
int n,g;
int m[2][10001];

ifstream in("rucsac.in");
ofstream out("rucsac.out");

void citire()
{
    int i;
    in>>n>>g;
    for(i=1;i<=n;i++)
        in>>v[i].w>>v[i].p;
}

void matrice()
{
    int i,j;
    bool l1=true,l2;
    for(i=1;i<=n;i++)
    {
        l2=l1;
        l1=!l1;
        for(j=1;j<v[i].w;j++)
            m[l1][j]=m[l2][j];
        for(;j<=g;j++)
            m[l1][j]=max(m[l2][j],m[l2][j-v[i].w]+v[i].p);
    }
    out<<m[l1][g];
}

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