#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int n,gr;

struct ob{
int g,v;
}v[5001];

int dp[10003];

int main()
{
    f >> n >> gr;
    for(int i = 1;i<=n;i++)
    {
        f >> v[i].g >> v[i].v;
    }
    for(int i = 1;i<=n;i++)
    {
        int g_curent = v[i].g;
        int v_curent = v[i].v;
        for(int j = gr;j>=1;j--)
        {
            if(j-g_curent>=0)
                dp[j] = max(dp[j],dp[j-g_curent]+v_curent);
        }
    }
    g << dp[gr];
}