#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e3 + 5;
const int GMAX = 1e4 + 5;
int n, w;
int dp[2][GMAX];
struct obiect {
    int w, p;
}v[NMAX];

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

    // dp[i][j] = profitul maxim la pasul i cu masa j
    dp[1][0] = 0;
    for(int i = 1; i <= n; ++i) {
        int k = i % 2;
        for(int j = 0; j <= w; ++j) {
            dp[k][j] = dp[1 - k][j];
            if(j >= v[i].w) {
                dp[k][j] = max(dp[k][j], dp[1 - k][j - v[i].w] + v[i].p);
            }
        }
    }

    g << dp[n % 2][w] << '\n';

    f.close();
    g.close();
    return 0;
}