#include <iostream>
#include <fstream>
#include <queue>
#include <tuple>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int LMAX = 10005;
const int NMAX = 5005;
int dp[2][LMAX], weight[NMAX], profit[NMAX];

int main() {
    int n, g, i, j, k;
    fin>>n>>g;
    for (i = 1; i <= n; i++) {
        fin>>weight[i]>>profit[i];
    }
    for (k = 1; k <= n; k++) {
        i = (k&1);
        for (j = 1; j <= g; j++) {
            //nu folosesc obiectul i
            dp[i][j] = dp[1 - i][j];

            if (j >= weight[k] && dp[1 - i][j - weight[k]] + profit[k] > dp[i][j])
                dp[i][j] = dp[1 - i][j - weight[k]] + profit[k]; //folosesc obiectul
        }
    }
    fout<<dp[(n&1)][g];


    fin.close();
    fout.close();
    return 0;
}