///Knapsack problem, time and space complexity O(C * N), possible space optimization: O(N)
///Note: for printing the items, change i % 2 and (i - 1) % 2 with i and i - 1 respectively and change the size of the dp array
///Commented lines with // are used as replacements for the line bellow for the memory optimization

#include <fstream>
#include <vector>

using namespace std;

ifstream in ("rucsac.in");
ofstream out ("rucsac.out");

class Knapsack{
public:
    int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity){
        ///is answer redundant?
        if(capacity <= 0 || profits.empty() || weights.size() != profits.size()){
            return 0;
        }
        int n = profits.size();
        vector<vector<int>> dp(2, vector<int>(capacity + 1));
        ///initialize with '0' dp[i][0] for every 'i'
        for(int i = 0; i < n; i++){
            dp[i % 2][0] = 0;
            //dp[i][0] = 0;
        }
        ///only one weight?
        for(int c = 0; c <= capacity; c++){
            if(weights[0] <= c){
                dp[0][c] = profits[0];
            }
        }
        ///basically the main thing
        for(int i = 1; i < n; i++){
            for(int c = 1; c <= capacity; c++){
                int profit1 = 0, profit2 = 0;
                ///can we include the item?
                if(weights[i] <= c){
                    profit1 = profits[i] + dp[(i - 1)%2][c - weights[i]];
                    //profit1 = profits[i] + dp[i - 1][c - weights[i]];
                }
                ///what if we exclude it?
                profit2 = dp[(i - 1) % 2][c];
                //profit2 = dp[i - 1][c];
                ///take the maximum
                dp[i % 2][c] = max(profit1, profit2);
                //dp[i][c] = max(profit1, profit2);
            }
        }
        ///we found the maximum profit, but what about the items?
        //findItems(dp, weights, profits, capacity);
        return dp[1][capacity];
    }

private:
    void findItems(vector<vector<int>> &dp, const vector<int> &weights, const vector<int> &profits, int capacity){
        out << "Selected weights:";
        int totalProfit = dp[weights.size() - 1][capacity];
        for(int i = weights.size() - 1; i>0; i--){
            if(totalProfit != dp[i - 1][capacity]){
                out << " " << weights[i];
                capacity -= weights[i];
                totalProfit -= profits[i];
            }
        }
        if(totalProfit != 0){
            out << " " << weights[0];
        }
        out<<"\n";
    }
};

int main()
{
    int c, n, a, b;
    in >> n >> c;
    Knapsack ks;
    vector<int> profits;
    vector<int> weights;
    for(int i = 0; i < n; i++){
        in >> a >> b;
        weights.push_back(a);
        profits.push_back(b);
    }
    int maxProfit = ks.solveKnapsack(profits, weights, c);
    out << maxProfit;
    return 0;
}