//
//  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[10005];

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