#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int w[5100],p[5100],n,g,best[10100],x;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    cin>>n>>g;
    for(int i=1;i<=n;++i)
        cin>>w[i]>>p[i];

    for(int i=1;i<=n;++i)
        for(int j=g-w[i];j>=0;--j)
        {
            best[j+w[i]] = max(best[j+w[i]], best[j]+p[i]);
            x = max(x,best[j+w[i]]);
        }

    cout<<x;
    return 0;
}