//
//  main.cpp
//  1 kanpsack problem PD
//
//  Created by Razvan Vranceanu on 11/03/2020.
//  Copyright © 2020 Razvan Vranceanu. All rights reserved.
//

#include <fstream>
#define Gmax 10001
#define Nmax 5001

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int a[Nmax][Gmax],n, G, val[Nmax], wg[Nmax], i, j;

int main()
{
    //citire
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>wg[i]>>val[i];
    
    //initializare
    for(i=1;i<=n;i++)
        a[i][0]=0;
    //prima linie
    for(i=wg[1]; i<=G; i++)
        a[1][i]=val[1];
    
    for(i=2;i<=n;i++)
        for(j=0;j<=G;j++)
        {
            if(wg[i]>j) a[i][j]=a[i-1][j];
            else a[i][j]=max(a[i-1][j-wg[i]] + val[i], a[i-1][j] );
        }
    g<<a[n][G];
    return 0;
}