#include <bits/stdc++.h>
 
using namespace std;
int i,j,n,G,sol;
int v[5005],w[5005],m[10005];
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
 
    f>>n>>G;
    for(i=1;i<=n;i=i+1)
    {
        f>>w[i];
        f>>v[i];
    }
 
    for(i=1;i<=n;i=i+1)
    for(j=G;j>=0;j--)
        if(w[i]<=j)
        m[j]=max(m[j],m[j-w[i]]+v[i]);
    g<<m[G];
 
 
    return 0;
}