#include <stdio.h>
#include <stdlib.h>
#define MEM1 110
#define MEM2 1024

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

int main(void) {

    // 入力

    int N, W;
    scanf("%d %d", &N, &W);

    int
        v_arr[MEM1],
        w_arr[MEM1];

    for (int i = 0; i < N; i++) scanf("%d %d", &v_arr[i], &w_arr[i]);

    // 計算

    int* max_values[MEM1];
    
    for (int i = 0; i < MEM1; i++) {
        max_values[i] = (int *)calloc( W+1, sizeof(int) );
        // max_values[i+1][w] := i番目までの品物から重さがwを超えないように選んだ時の価値の総和の最大値
    }

    // 初期化: 0番目のときの-1番目に関する価値 -> 全て0
    for (int w = 0; w <= W; w++) max_values[0][w] = 0; 

    for (int i = 0; i < N; i++) {
        for (int w = 0; w <= W; w++) {
            if (w >= w_arr[i]) {
                max_values[i+1][w] = max2( max_values[i][w - w_arr[i]] + v_arr[i], max_values[i][w] );
                // この商品を取った時の価値と取らずにwまで取った時の最大値を比べる。
            } else {
                max_values[i+1][w] = max_values[i][w];
                // この商品はもう取れないので取らなかったときの値が最大
            }
        }
    }

    // 出力

    printf("%d\n", max_values[N][W]);

    for (int i = 0; i < MEM1; i++) {
        free(max_values[i]);
    }

    return 0;
}
