"use strict";
function Main(input) {
    let lines = input.split("\n");
    let nw = lines.shift().split(/\s/).map((v) => v - 0);
    let N = nw[0] - 0, W = nw[1] - 0;
    let wv = new Array(N);
    for (let n = 0; n < N; n++) {
        wv[n] = lines.shift().split(/\s/).map((v) => v - 0);
    }
    let dp = new Array(N + 1).fill(0).map(() => new Array(W + 1).fill(0));
    for (let n = 0; n < N; n++) {
        for (let sum_w = 0; sum_w <= W; ++sum_w) {
            if (sum_w - wv[n][0] >= 0) {
                dp[n + 1][sum_w] = Math.max(dp[n + 1][sum_w], dp[n][sum_w - wv[n][0]] + wv[n][1]);
            }
            dp[n + 1][sum_w] = Math.max(dp[n + 1][sum_w], dp[n][sum_w]);
        }
    }
    console.log(dp[N][W]);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
/*
N	W
6	15

w	v
6	5
5	6
6	4
6	6
3	5
7	2

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	5	5	5	5	5	5	5	5	5	5
2	0	0	0	0	0	6	6	6	6	6	6	11	11	11	11	11
3	0	0	0	0	0	6	6	6	6	6	6	11	11	11	11	11
4	0	0	0	0	0	6	6	6	6	6	6	12	12	12	12	12
5	0	0	0	5	5	6	6	6	11	11	11	12	12	12	17	17
6	0	0	0	5	5	6	6	6	11	11	11	12	12	12	17	17
*/
