#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;
    /// stare = 0 linie anterioara
    /// stare = 1 linie curenta
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= gmax; j++){
            dp[1][j] = dp[0][j];
            if(j >= w[i]){
                dp[1][j] = max(dp[0][j],dp[0][j - w[i]] + p[i]);
            }
        }
        for(int j = 1; j <= gmax; j++)
            dp[0][j] = dp[1][j];
    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= gmax; j++)
//            cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }
    out<<dp[1][gmax];
//    cout<<dp[n][gmax]<<endl;
    return 0;
}