#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int mat[5005][10005];
int vet[5005];
int profit[5005];
int main() {
    int n, g, i, j, max = 0;
    in >> n >> g;
    mat[0][0] = 1;
    for (i = 1; i <= n; i++) {
        in >> vet[i] >> profit[i];
        for (j = vet[i]; j <= g; j++) {
            if (mat[i - 1][j] > mat[i - 1][j - vet[i]] + profit[i] && mat[i - 1][j] > 0)
                mat[i][j] = mat[i - 1][j];
            else if (mat[i][j - vet[i]] > 0)
                mat[i][j] = mat[i - 1][j - vet[i]] + profit[i];
            if (i == n && mat[i][j] > max)
                max = mat[i][j];
        }
    }
    out << max - 1;
}