#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int n,w;
int dp[10001][5001];
int gr,cost;
int main()
{
    f >> n>> w;
    for(int i= 1;i<=n;i++)
    {
        f >> gr >> cost;
        for(int j = 1;j<gr;j++)
        {
            dp[i][j] = dp[i-1][j];
        }
        for(int j = gr;j<=w;j++)
            dp[i][j] =  max(dp[i-1][j],dp[i-1][j-gr]+cost);

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