#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
long long n,w,g[5005],v[5005],val[10005],smax;
const int MOD=1e9+7;
int main()
{
    fin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        fin>>g[i]>>v[i];
    }
    fill(val,val+w+1,-1);
    val[0]=0;
    for (int k = 1; k <= n; k++) 
    {
        for (int x = w; x >= 0; x--) 
        {
            if (val[x]>=0&&x+g[k]<=w) {val[x+g[k]] = val[x]+v[k];}
        }
    }
    for(int i=1;i<=w;i++)
    {
        smax=max(smax,val[i]);
    }
    fout<<smax;
fin.close();
fout.close();
    return 0;
}