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

using namespace std;

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

int n, gmax;
vector<int>g;
vector<int>v;
int rezultat;

int KS(int nr_obiecte, int greutate_rucsac)
{
    vector<vector<int>>matrice(nr_obiecte + 1, vector<int>(greutate_rucsac + 1));
    
    for(int i = 0; i <= nr_obiecte; i++)
    {
        for(int j = 0; j <= greutate_rucsac; j++)
        {
            if(i == 0 || j == 0)
                matrice[i][j] = 0;
            else if(g[i] <= j)
                matrice[i][j] = max(v[i] + matrice[i - 1][j - g[i]], matrice[i - 1][j]);
            else 
                matrice[i][j] = matrice[i - 1][j];
        }
    }
        return matrice[nr_obiecte][greutate_rucsac];
}

int main()
{
    f >> n >> gmax;
    
    g.resize(n + 1, 0);
    v.resize(n + 1, 0);
    
    for(int i = 1; i <= n; i++)
        f >> g[i] >> v[i];
        
    o << KS(n, gmax);

    return 0;
}