#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 ' '
string file = "rucsac";
ifstream f(file + ".in");
ofstream g(file + ".out");

int n, G;
vector<int> p, w;
vector<int> dp;

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

int proc()
{
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = G - w[i]; j >= 0; j--)
            if (dp[j] != -1 && dp[j + w[i]] < dp[j] + p[i])
                dp[j + w[i]] = dp[j] + p[i];
    int ans = 0;
    for (int i = 1; i <= G; i++)
        ans = max(ans, dp[i]);
    return ans;
}

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