#include <cstdio>
#include <iostream>

using namespace std;

const int nmx = 5002;
const int gmx = 10002;

int items, max_weight, total_weight;
int weight[nmx], value[nmx];
int dp[gmx];

void input()
{
    scanf("%d %d", &items, &max_weight);
    for(int i = 1; i <= items; ++i)
        scanf("%d %d", &weight[i], &value[i]);
}

void dynamic()
{
    for(int i = 1; i <= items; ++i)
    {
        total_weight = min(total_weight + weight[i], max_weight);

        for(int j = total_weight; j >= weight[i]; --j)
            dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
    }
}

void output()
{
    printf("%d\n", dp[total_weight]);
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    input();
    dynamic();
    output();
    return 0;
}