#include <fstream>
using namespace std;

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

int dp[5005][10005], n, G, w[5005], p[5005];

int maxim(int a, int b) {
    if(a > b)
        return a;
    return b;
}

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

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= G; j++) {
            if(j >= w[i])
                dp[i][j] = maxim(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
            else
                dp[i][j] = dp[i-1][j];
        }


    g << dp[n][G];
}