#include <iostream>
#include <set>
#include <vector>
#include <fstream>

using namespace std;

bool isPossible(vector<int> S, int L)
{
    bool p[10001];
    p[0] = true;
    for(int i = 0 ; i < S.size(); i++)
    {
        for(int j = L ; j >= 0; j--)
        {
            if(p[j] && j + S[i] <= L)
            {
                p[j + S[i]] = true;
            }
        }
    }
    return p[L];
}

long long d[3][10001];

int w[5001];
int p[5001];
int main()
{
    vector<int> S;
    S.push_back(2);
    S.push_back(2);
    S.push_back(3);
    S.push_back(5);
    S.push_back(8);
    S.push_back(23);
    S.push_back(22);
    S.push_back(45);
    int L = 46;
   // cout<<isPossible(S, L);

    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n,g;
    fin>>n>>g;
    for(int i = 1; i <= n; i++)
    {
        fin>>w[i]>>p[i];
        //d[i][w[i]] = p[i];
    }
    for(int i = 1, k = 1; i <= n; k = 1 - k, i++)
        for(int j = 0; j <= g; j++)
            if(j - w[i] >= 0)
               d[k][j] = max(d[1-k][j],d[1-k][j - w[i]] + p[i]);
            else d[k][j] = d[1-k][j];
    fout<<d[n%2][g];
    return 0;
}