#include <iostream>
#include <fstream>
#define maxn 5001
#define maxg 10001

using namespace std;

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int n,G;
    int max=0;
    int w[maxn],p[maxn],din[maxg];
    f >> n >> G;
    for (int i=0;i<n;i++)
    {
        f >> w[i] >> p[i];
    }
    fill(din,din+G+1,-1);
    din[0] = 0;
    for (int j=0;j<n;j++)
    {
         for (int i=G;i>=0;i--)
        {
            if(din[i]>=0 && i+w[j]<=G && din[i]+p[j]>din[i+w[j]])
            {
                din[i+w[j]] = din[i] + p[j];
                if (din[i+w[j]] > max)
                    max = din[i+w[j]];
            }
        }
    }
    g << max;

    return 0;
}