#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream out("rucsac.out");

void initialize(int v[], int p[], int G)
{
    for(int i = 0; i<= G; i++)
    {
        v[i] = 0;
        p[i] = 0;
    }
}

void print_vec(int v[], int n)
{
    for(int i = 0; i<n; i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

int get_max(int x, int y)
{
    if(x > y)
        return x;
    return y;
}

int main()
{
    int n, G, current_g, current_v;

    fin>>n>>G;

    int p[G + 1], v[G + 1];
    initialize(v, p, G);

    for(int i = 0; i<n; i++)
    {
        fin>>current_g>>current_v;

        for(int j = 0; j<=G; j++)
        {
            if(current_g > j)
                v[j] = p[j];
            else
                v[j] = get_max(p[j], p[j - current_g] + current_v);
        }

        for(int k = 0; k<=G; k++)
        {
            p[k] = v[k];
        }
    }

    out<<v[G];

    return 0;
}