#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, gr, w, i, cost[2][10001], wei[5001], cos[5001], j;
int main()
{
    f>>n>>w;
    for (i=1; i<=n; i++)
        f>>wei[i]>>cos[i];
    for (i=1; i<=n; i++) {
        for (gr=0; gr<=w; gr++) {
            cost[j][gr]=cost[1-j][gr];
            if (wei[i] <= gr)
                cost[j][gr]=max(cost[j][gr], cost[1-j][gr-wei[i]]+cos[i]);
        }
        j=1-j;
    }
    g<<cost[1][w];
    return 0;
}