#include <bits/stdc++.h>

using namespace std;

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

int n, G;
int P[5001], W[5001], sol[10001];

int main()
{
    fin>>n>>G;
    for(int i=1; i<=n; ++i) fin>>W[i]>>P[i];
    sol[0]=0;
    for(int i=1; i<=n; ++i)
    {
        for(int j=G; j>=W[i]; --j)
        {
            sol[j]=max(sol[j], sol[j-W[i]]+P[i]);
        }
    }
    fout<<sol[G]<<"\n";
    return 0;
}