#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    long long n, capacity;
    scanf("%lld %lld", &n, &capacity);

    long long value[n], profit[n];

    for (long long i = 0; i < n; i++) {
        scanf("%lld %lld", &value[i], &profit[i]);
    }

    long long dp[capacity + 1];

    for (long long i = 0; i <= capacity; i++) {
        dp[i] = 0;
    }

    for (long long i = 0; i < n; i++) {
        for (long long j = capacity; j >= value[i]; j--) {
            dp[j] = max(dp[j], dp[j - value[i]] + profit[i]);
        }
    }

    printf("%lld\n", dp[capacity]);

    return 0;
}