#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[5001][10001];

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


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

    }
    g<<dp[n][G];

    return 0;
}