//https://www.infoarena.ro/problema/rucsac

#include <fstream>

using namespace std;
int weight[10005];
int profit[10005];
int tableValues[5005][5005];

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    int object, maxWeight, ans = -100000;

    fin >> object >> maxWeight;

    for (int i = 1; i <= object; ++i) {
        fin >>  weight[i] >> profit[i];
    }
    for (int i = 1; i <= object; ++i) {
        tableValues[i][0] = 0;
    }
   
    for (int i = 1; i <= maxWeight; ++i){
        for (int j = 1; j <= object; ++j) {
            tableValues[i][j] = tableValues[i][j - 1];
            if (i - weight[j] < 0) { 
                tableValues[i][j] = max(tableValues[i][j - 1], tableValues[i - weight[j]][j - 1] + profit[j]);
            }
            if (ans <= tableValues[i][j]) {
                ans = tableValues[i][j];
            }
        }
    }
    fout << ans;   
}