#include<iostream>
#include<fstream>

using namespace std;

int ct[3][10001];
int G[5001],C[5001];

int main(){

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

    int n,g,l=0, i, j;
    in>>n>>g;

for(i=1;i<=n;i++)
    in>>G[i]>>C[i];

for(i=1;i<=n;i++)
{
    for(j=1;j<=g;j++)
        {
        ct[1-l][j]=ct[l][j];
        if(G[i]<=j)
            if(C[i]+ct[l][j-G[i]]>ct[1-l][j])
                ct[1-l][j]=C[i]+ct[l][j-G[i]];
            else
                ct[1-l][j]=ct[1-l][j];
        }
        l=1-l;
}
    out<<ct[l][g];
    return 0;
}