#include <bits/stdc++.h>

std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");

const int SIZE = 5e3 + 5;
const int MAXWEIGHT = 1e4 + 5;

int n, W;
int profit[SIZE], weight[SIZE];
int dp[MAXWEIGHT];
int ans;

int64_t max(std::vector<int64_t> v){ return *std::max_element(v.begin(), v.end()); }
int64_t min(std::vector<int64_t> v){ return *std::min_element(v.begin(), v.end()); }

int main() 
{
    fin >> n >> W;
    for(int i = 1; i <= n; ++i)
        fin >> weight[i] >> profit[i];

    for(int i = 1; i <= n; ++i)
        for(int j = W; j >= weight[i]; --j)
        {
            dp[j] = max({dp[j], dp[j - weight[i]] + profit[i]});
            ans = max({ans, dp[j]});
        }
    
    fout << ans;

    return 0;
}