#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_IN "rucsac.in"
#define FILE_OUT "rucsac.out"
#define ITEM_AMOUNT 5000
#define WEIGHT_MAX 10000

int values[ITEM_AMOUNT + 1], weights[ITEM_AMOUNT + 1];
int *m;
int n, w;

int max(int a, int b) {
    return a > b ? a : b;
}

void printArray(int *arr, int len, int split) {
	int c = 0;
	for(int i = 0; i < len; i++) {
		printf("%d ", arr[i]);
		c++;
		
		if(c == split && split != -1) {
			printf("\n");
			c = 0;
		}
	}
	printf("\n");
}

int main()
{
    FILE *fileIn = fopen(FILE_IN, "r"),
         *fileOut = fopen(FILE_OUT, "w");

    fscanf(fileIn, "%d%d", &n, &w);
    for(int i = 1; i <= n; i++) {
        fscanf(fileIn, "%d%d", &weights[i], &values[i]);
    }
	m = malloc(sizeof(int) * (w + 1) * 2);
    
    for(int j = 0; j <= w; j++) {
        m[j] = 0;
    }
    m[w + 1] = 0;
	
	printArray(m, (w + 1) * 2, w + 1);
	//printf("\n");
    
    for(int i = 1; i <= n; i++) {
		printArray(m, (w + 1) * 2, w + 1);
		//printf("\n");
		
        for(int j = 1; j <= w; j++) {
            if(weights[i] > j) m[w + j] = m[j];
            else m[w + j] = max(m[j], m[j - weights[i]] + values[i]);
        }
		//m = memcpy(m, m + w, sizeof(int) * (w + 1));
		for(int k = 0; k <= w; k++) {
			m[k] = m[w + k];
		}
		
		printArray(m, (w + 1) * 2, w + 1);
		//printf("\n");
    }
	
    fprintf(fileOut, "%d\n", m[2 * w]);
	
	free(m);
    fclose(fileIn);
    fclose(fileOut);
    return 0;
}