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

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, greutate;
int gr[5001], pret[5001];
int dp[10001];

void citire()
{
    fin >> n >> greutate;
    for(int i = 1; i <= n; ++i)
        fin >> gr[i] >> pret[i];
}

int pret_minim()
{
    for(int i = 1; i <= n; ++i)
        for(int j = greutate; j > 0 && j - gr[i] >= 0; --j)
            dp[j] = max(dp[j], dp[j - gr[i]] + pret[i]);

    return dp[greutate];
}

int main()
{
    citire();
    fout << pret_minim();
    return 0;
}