#include <iostream>
#include <fstream>
#define fin "rucsac.in"
#define fou "rucsac.out"
using namespace std;
ifstream t1(fin);
ofstream t2(fou);
int w[5001],v[5001],tab[10001];

int maxim(int a,int b)
{
    if(a>b) return a;
    else return b;
}

int main()
{
    int n,g,maximum=-1;
    t1>>n>>g;
    int i,j,i2;
    for(i=1;i<=n;i++) t1>>w[i]>>v[i];
    for(i=1;i<=n;i++)
    {
        for(j=g-w[i];j>=0;j--)
        if(tab[j+w[i]]<tab[j]+v[i]) { tab[j+w[i]]=tab[j]+v[i]; if(maximum<tab[j+w[i]]) maximum=tab[j+w[i]]; }
    }
    t2<<maximum<<'\n';
    t1.close();
    t2.close();
    return 0;
}