//
//  main.cpp
//  Rucsac
//
//  Created by Darius Buhai on 10/11/2018.
//  Copyright © 2018 Darius Buhai. All rights reserved.
//

/*
 este nevoie de matrice deoarece avem atat greutate cat si valoare
 dp[i-1][j] | dp[i-1][j-g]+pc
 i = nr obiecte
 j = greutate
 
    0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10
 0  0  0  0  7  7  7  7  7  7  7  7
 1  0  0  0  7  7  7 11 11 11 11 11
 2  0  2  2  7  9  9  9 13 13 13 13
 3  0  9  9  7 11 11 11 13 24 24 24
 4  0  9 18 18
 5
 6
*/

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

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

int n,g, w,p;

int dp[5001][10001];

int main() {
    fin>>n>>g;
    fin>>w>>p;
    for(int j=w;j<=g;j++)
        dp[0][j] = p;
    for(int i=1;i<n;i++)
    {
        fin>>w>>p;
        for(int j=w;j<=g;j++){
            if(dp[i-1][j-w]+p > dp[i-1][j])
                dp[i][j] = dp[i-1][j-w]+p;
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    fout<<dp[n-1][g];
    return 0;
}