#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n,g,ans = 0;
    fin >> n >> g;
    for (int i = 0;i < n;i++)
        fin >> v[i].w >> v[i].p;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j <= g;j++) {
            if (j >= v[i].w)
                dp[(i & 1)][j] = max(dp[((i & 1) ^ 1)][j], dp[((i & 1) ^ 1)][j - v[i].w] + v[i].p);
            else
                dp[(i & 1)][j] = dp[((i & 1) ^ 1)][j];
            ans = max(ans, dp[(i & 1)][j]);
        }
    }
    fout << ans;
    return 0;
}