#include <bits/stdc++.h>

using namespace std;

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

const int N = 5e3 + 1, G = 1e4 + 1;
int n, greutate, w[N], p[N], dp[G], best; // dp[i] = profitul maxim pt. elemente de greutate totala i

int main(){
    f >> n >> greutate;
    for(int i = 0; i < n; i++)
        f >> w[i] >> p[i];

    f.close();
    for(int i = 1; i <= greutate; i++)
        dp[i] = -1;

    for(int i = 0; i < n; i++){
        for(int j = greutate - w[i]; j >= 0; j--){
            if(dp[j] != -1) // daca exista un profit pt. elemente de greutate j
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
        }
    }

    for(int i = 1; i <= greutate; i++)
        best = max(best, dp[i]);

    g << best;
    g.close();
}