#include <iostream>
#include <fstream>

const int MAXN = 5e3 + 5,MAXG = 1e4 + 1;

using namespace std;

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

int n,gmax,w[MAXN],p[MAXN];
int dp[2][MAXG];

int main()
{
    in>>n>>gmax;
    for(int i = 1; i <= n; i++)
        in>>w[i]>>p[i];
    int stare = 1;
    /// starea alterneaza
    /// pentru a lua starea anteriora fac stare - 1
    for(int i = 1; i <= n; i++){
        int stare_ant = stare;
        stare = 1 - stare;
        for(int j = 1; j <= gmax; j++){
            dp[stare][j] = dp[stare_ant][j];
            if(j >= w[i]){
                dp[stare][j] = max(dp[stare_ant][j],dp[stare_ant][j - w[i]] + p[i]);
            }
        }
    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= gmax; j++)
//            cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }
    out<<dp[stare][gmax];
//    cout<<dp[n][gmax]<<endl;
    return 0;
}