#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v;
int n,w,W,V,L,R,low=-100000000;
int main()
{
    freopen("rucsac.in","r",stdin);freopen("rucsac.out","w",stdout);cin>>n>>w;v.assign(w+1,low);v[0]=0;
    for(;n;n--){cin>>W>>V;R=L=w;L-=W;for(;L+1;R--,L--)v[R]=max(v[R],v[L]+V);}
    for(R=1,V=0;R<=w;R++)V=max(V,v[R]);printf("%d\n",V);return 0;
}