// Slower C++ solution:
/**

 * code generated by JHelper

 * More info: https://github.com/AlexeyDmitriev/JHelper

 * @author YahiaAshraf74

 */



#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <unordered_set>

#include <unordered_map>

#include <queue>

#include <stack>

#include <complex>

#include <string>

#include <bitset>

#include <stdio.h>

#include <string.h>

#include <fstream>

#include <iomanip>

#include <assert.h>



using namespace std;

#define el  '\n'

#define ll long long

#define clr(a, b)memset(a,b,sizeof(a))

#define sz(a) (int)(a).size()

const long long N = 102, OO = 0x3f3f3f3f, MOD = (int) 1e9 + 7;



ll dp[2][(int) 1e5 + 2];



class DKnapsack1 {

public:

    void init() {

        clr(dp,0);

    }



    void solve(istream &cin, ostream &cout) {

        init();

        int n, totW;

        cin >> n >> totW;

        bool first = true;

        for (int j = 0; j < n; j++) {

            int w, v;

            cin >> w >> v;

            first = true;

            for (int curW = 0; curW <= totW; curW++) {

                int i = j%2;

                if (first) {

                    first = false;

                    dp[i % 2][curW] = (curW - w >= 0) ? v : 0;

                    continue;

                }

                if (curW - w >= 0)

                    dp[i][curW] = max(dp[(((i - 1) % 2 + 2) % 2)][curW], dp[(((i - 1) % 2 + 2) % 2)][curW - w] + v);

                else

                    dp[i][curW] = dp[(((i - 1) % 2 + 2) % 2)][curW];

            }

        }



        cout << dp[(((n - 1) % 2 + 2) % 2)][totW] << el;

    }

};

int main() {

	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);

	DKnapsack1 solver;

	std::istream& in(std::cin);

	std::ostream& out(std::cout);

	solver.solve(in, out);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.586412346371305x):
/**

 * code generated by JHelper

 * More info: https://github.com/AlexeyDmitriev/JHelper

 * @author YahiaAshraf74

 */



#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <set>

#include <map>

#include <unordered_set>

#include <unordered_map>

#include <queue>

#include <stack>

#include <complex>

#include <string>

#include <bitset>

#include <stdio.h>

#include <string.h>

#include <fstream>

#include <iomanip>

#include <assert.h>



using namespace std;

#define el  '\n'

#define ll long long

#define clr(a, b)memset(a,b,sizeof(a))

#define sz(a) (int)(a).size()

const long long N = 102, OO = 0x3f3f3f3f, MOD = (int) 1e9 + 7;



ll dp[2][(int) 1e5 + 2];



class DKnapsack1 {

public:

    void init() {

        clr(dp,0);

    }



    void solve(istream &cin, ostream &cout) {

//        init();

        int n, totW;

        cin >> n >> totW;

        bool first = true;

        for (int j = 0; j < n; j++) {

            int w, v;

            cin >> w >> v;

            first = true;

            for (int curW = 0; curW <= totW; curW++) {

                int i = j%2;

                if (first) {

                    first = false;

                    dp[i % 2][curW] = (curW - w >= 0) ? v : 0;

                    continue;

                }

                if (curW - w >= 0)

                    dp[i][curW] = max(dp[(((i - 1) % 2 + 2) % 2)][curW], dp[(((i - 1) % 2 + 2) % 2)][curW - w] + v);

                else

                    dp[i][curW] = dp[(((i - 1) % 2 + 2) % 2)][curW];

            }

        }



        cout << dp[(((n - 1) % 2 + 2) % 2)][totW] << el;

    }

};

int main() {

	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);

	DKnapsack1 solver;

	std::istream& in(std::cin);

	std::ostream& out(std::cout);

	solver.solve(in, out);

	return 0;

}