#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef size_t ull;
typedef vector<int> vc;
typedef vector<vector<int>> matrix;
#define ft(n) for(int i=1; i<=n; i++)
#define sp ' '
#define vx first
#define vy second
string file = "rucsac";
ifstream f(file + ".in");
ofstream g(file + ".out");

int n, G;
vector<int> p, w;
vector<int> dp1, dp2;

void test2d(matrix v)
{
    g << endl;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 0; j <= G; j++)
        {
            g << v[i][j] << " ";
        }
        g << endl;
    }
}

void init()
{
    f >> n >> G;
    p.resize(n + 1, 0);
    w.resize(n + 1, 0);
    ft(n)
        f >> w[i] >> p[i];
    dp1.resize(G + 1, 0);
    dp2.resize(G + 1, 0);
}

int proc()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= G; j++)
        {
            if (i % 2 == 1)
            {
                dp2[j] = dp1[j];
                if (j >= w[i])
                    dp2[j] = max(dp2[j], dp1[j - w[i]] + p[i]);
            }
            else
            {
                dp1[j] = dp2[j];
                if (j >= w[i])
                    dp1[j] = max(dp1[j], dp2[j - w[i]] + p[i]);
            }

        }
    }
    int ans = 0;
    for (int i = 1;i <= G;i++)
    {
        dp1[i] = max(dp1[i], dp2[i]);
        ans = max(ans, dp1[i]);
    }
    return ans;
}


int main()
{
    init();
    g << proc();
    return 0;
}