#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("rucsac.in", "r"), *G=fopen("rucsac.out", "w");

int n, W, w[5005], p[5005], a[3][10003];

int main()
{
    fscanf(F, "%d %d ", &n, &W);
    for(int i = 1; i <= n; ++ i) fscanf(F, "%d %d ", &w[i], &p[i]);
    for(int i = 1; i <= n; ++ i)
        if(i % 2)
            for(int j = 1; j <= W; ++ j)
            {
                if(j >= w[i])
                    a[0][j] = max(a[1][j-w[i]]+p[i], a[1][j]);
                else a[0][j] = a[1][j];
            }
        else
            for(int j = 1; j <= W; ++ j)
            {
                if(j >= w[i])
                    a[1][j] = max(a[0][j-w[i]]+p[i], a[0][j]);
                else a[1][j] = a[0][j];
            }
    fprintf(G, "%d", a[1][W]);
    return 0;
}