#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[MAXN][MAXG];
/// dp[i][j] = profitul maxim cu primele i produse avand greutate cel mult j
/// daca vreau exact j trebuie sa am grija la prima linie

int main()
{
    in>>n>>gmax;
    for(int i = 1; i <= n; i++)
        in>>w[i]>>p[i];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= gmax; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i]){
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][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[n][gmax];
//    cout<<dp[n][gmax]<<endl;
    return 0;
}