#include <stdio.h>
#include <fstream>
using namespace std;

int n, g_max;
int pr[5010];
int gr[5010];
int matr[5010][10020];

void citeste() {
     ifstream f("rucsac.in");
     f >> n >> g_max;
     for (int i = 0; i < n; i++) {
         f >> gr[i] >> pr[i];
     }
     f.close();     
}

int max(int a, int b) {
    return (a > b ? a : b);
}

int rezolva() {
    // Completez prima linie resp coloana
    for (int i = 0; i <= g_max; i++) {
        if (gr[0] <= i) {
           matr[0][i] = pr[0];
        } else {
           matr[0][i] = 0;
        }
    }
    // Completez restul matricei
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= g_max; j++) {
            matr[i][j] = max(matr[i-1][j], matr[i-1][j - gr[i]] + pr[i]);
        }
    }
    return matr[n-1][g_max];
}

void afiseaza(int rez) {
     ofstream g("rucsac.out");
     g << rez;
     g.close();     
}

int main()
{
    int rez;
    citeste();
    rez = rezolva();
    afiseaza(rez);
}