#include <bits/stdc++.h>

using namespace std;

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



struct obiect {
    int w, p;
}ob[5001];

int dp[5001][10001], n, g;

int main() {

    f >> n >> g;

    for(int i = 1; i <= n; ++ i)
        f >> ob[i].w >> ob[i].p;

    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= g; ++j) {
            dp[i][j] = dp[i-1][j];

            if(ob[i].w <= j)
                dp[i][j] = max(dp[i-1][j-ob[i].w] + ob[i].p, dp[i][j]);
        }


    fout << dp[n][g];




    return 0;
}