#include <iostream>
#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream gout("rucsac.out");
int n,G,i,g[5010],p[5010],optim[10011],j;
int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>g[i]>>p[i];
    optim[0]=0;
    for(i=1;i<=n;i++)
        for(j=G-g[i];j>=0;j--)
        if(optim[j] + p[i] > optim[j+g[i]])
    {
        optim[j+g[i]]=optim[j] + p[i];
    }
    gout<<optim[G];
}