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

typedef struct items {
    int weight;
    int value;
} Item;

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

int main () {
    FILE *in = fopen("rucsac.in", "r");
    FILE *out = fopen("rucsac.out", "w");

    int n, W;
    fscanf(in, "%d %d", &n, &W);
    Item *items = malloc(n * sizeof(Item));
    for (int i = 0; i < n; i++) {
        fscanf(in, "%d %d", &items[i].weight, &items[i].value);
    }

    int **dp = calloc((n + 1), sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = calloc((W + 1), sizeof(int));
    }

    for (int i = 1; i <= n; i++) {
        for (int cap = 0; cap <= W; cap++) {
            if (items[i].weight > cap) {
                dp[i][cap] = dp[i - 1][cap];

            } else {
                dp[i][cap] = max(dp[i - 1][cap - items[i - 1].weight] + items[i - 1].value,
                                    dp[i - 1][cap]);
            }
        }
    }

    fprintf(out, "%d", dp[n][W]);

    return 0;
}