#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e4 +7;
const int DIM2 = 5007;

int dp[2][DIM];

pair <int,int> v[DIM2];

int main()
{
    int n, g;
    in >> n >> g;

    for(int i = 1; i <= n; i++)
    {
        int x, y;
        in >> x >> y;

        v[i] = {x,y};
    }

    int l = 1;

    for(int i = 1; i <= n; i++)
    {
        l = 1 - l;

        int w = v[i].first;
        int p = v[i].second;

        for(int j = 0; j <= g; j++)
        {

         dp[1 - l][j] = dp[l][j];
         if(w <= j)
         dp[1 - l][j] = max(dp[1 - l][j],dp[l][j - w] + p);
        }

    }

    out << dp[n % 2][g];
    return 0;
}