#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("rucsac.in");
ofstream out("rucsac.out");
 
const int N = 5005;
const int G = 10005;

int dp[G];
int price[N];
int weight[N];
 
int main()
{
    int n, g;
    in >> n >> g;
 
    for(int i = 1; i <= n; ++i)
        in >> weight[i] >> price[i];
 
    int max_w = 0, sol = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = max_w; j >= 0; --j)
            if(j + weight[i] <= g && dp[j] + price[i] > dp[j + weight[i]]) {
                if(j + weight[i] > max_w)
                    max_w = j + weight[i];

                dp[j + weight[i]] = dp[j] + price[i];

                if(dp[j + weight[i]] > sol)
                    sol = dp[j + weight[i]];
            }
    }
 
    out << sol;
    return 0;
}