#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int n,G,v[5001],w[5001],s[10001];

int main()
{
    int i,j;
    fin>>n>>G;
    for (i=1;i<=n;i++) fin>>w[i]>>v[i];
    for (i=1;i<n;i++)
    {
        for (j=G;j>=w[i];j--)
        if (s[j-w[i]]+v[i]>s[j]) s[j]=s[j-w[i]]+v[i];
    }
    s[G]=s[G-w[n]]+v[n];
    fout<<s[G];
}