#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 = G-w[i]; j >= 0; j--)
                dp[i][j+w[i]] = maxim(dp[i-1][j+w[i]], dp[i-1][j]+p[i]);



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