#include <iostream>
#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G;
int p[5001],w[5001];
int dp[5][10001];

void Citire(){
    f>>n>>G;
    for(int i=1;i<=n;i++)
        f>>w[i]>>p[i];
}


int main()
{
    Citire();

    int lin=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=G;j++){
            dp[lin][j] = (w[i]<=j) ? max(dp[lin^1][j],dp[lin^1][j-w[i]]+p[i]) : dp[lin^1][j];
        }
        lin=lin^1;
    }
    g<<dp[lin^1][G];

    return 0;
}