#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 5005
#define MAX_W 10005

/* N - no. of items
   W - max weight */
int N, W;

/* prices and weights */
int weight[MAX_N], price[MAX_N];

/* D[i][w] -> max profit you get with first a
   subset of first i items that weight under
   w pounds. Only 2 lines since you only need
   to keep the values for previous i - 1 values. */
int DP[2][MAX_W];

int main() {
	freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf ("%d%d", &N, &W);
    for (int i = 1; i <= N; i++) {
    	scanf("%d%d", &weight[i], &price[i]);
    }

    /* Need to keep track of where (what line) the previous 
       information is kept, so keep alternating between 0 / 1. */
    int previousLine = 0;
    for (int i = 1; i <= N; i++, previousLine = 1 - previousLine) {
    	for (int j = 0; j <= W; j++) {
    		int currentLine = 1 - previousLine;
    		DP[currentLine][j] = DP[previousLine][j];
    		if (weight[i] <= j) {
    			DP[currentLine][j] = max (DP[currentLine][j], DP[previousLine][j - weight[i]] + price[i]);
    		}
    	}
    }

    printf("%d", DP[previousLine][W]);

    return 0;
}