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

int max(int a, int b)
{
    if (a >= b) return a;
    else return b;
}


int main(void)
{
    int N, W;
    int weight[1001] = {0};
    int value[1001] = {0};
    int dp[101][10001];
    int i, w;
    scanf("%d %d", &N, &W);
    for (i=0; i<N; ++i) {
        scanf("%d %d", &value[i], &weight[i]);
    }
    for (w=0;w<=W;++w) dp[0][w] = 0;

    for (i=0; i<N; ++i) {
        for (w=0;w<=W;++w) {
            if (w >= weight[i]) dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
            else dp[i+1][w] = dp[i][w];
        }
    }
    printf("%d\n", dp[N][W]);
}

