#include <iostream>
#include <fstream>
using namespace std;
int profit[10000],upp[10000],T[10000];
int main()
{   int gr[5000],pr[5000],maxim = 0;
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int n,G;
    f>>n>>G;
    for(int i =1;i<= n;i++)
        f>>gr[i]>>pr[i];
    T[0] = 1;
    upp[0] = 0;
    for(int i = 1;i<= n;i++){
        for(int j = G;j>= 0;j--){
            if(T[j] == 1 && j+gr[i]<=G){
                if(profit[j]+pr[i]>profit[j+gr[i]]){
                    int t = j+gr[i];
                    T[t] = 1;profit[t] = profit[j] + pr[i];
                    upp[t] = i;
                    if(profit[t] >maxim)
                    {
                        maxim = profit[t];
                    }
                }
            }
        }
    }
    g << maxim;
    return 0;
}