/*************

    ~LeTeutz~
    25 puncte
    O(n*m) memorie+timp

*************/

#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N,W;
int P[5001],G[5001];
int dp[5001][10001];

int main()
{
    f>>N>>W;
    for(int i=1; i<=N; i++)
        f>>G[i]>>P[i];

    for(int i=1; i<=N; ++i)
        for(int j=1; j<=W; ++j){
            dp[i][j] = dp[i-1][j];
            if( j-G[i] >= 0)
            dp[i][j] = max( dp[i-1][j] , dp[i-1][j-G[i]] + P[i]);
        }

    g<<dp[N][W]<<"\n";
    return 0;
}