#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n, P, i, j, profit[10001], p[5001], v[5001], Max;
int main ()
{
    in>>n>>P;
    for (i=1; i<=n; i++)
        {in>>p[i]>>v[i];}
    for (i=1; i<=n; i++)
            {profit[i]=-1;}
    for (i=1; i<=n; i++)
       {
        for (j=P-p[i]; j>=0; j--)
            {if (profit[j]+1) profit[j+p[i]]=max(profit[j+p[i]], profit[j]+v[i]);}
       }
    for (i=1; i<=P; i++)
       {
        if (profit[i]>Max)
            {Max=profit[i];}
       }
    out<<Max;
}