#include <fstream>
using namespace std;

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

int n, C, val[5001], w[5001], sol;
int dp[10001];

void Read();

int main()
{
    Read();
    for (int i = 0; i <= n; ++i)
        for (int j = C-w[i]; j >= 0; --j)
            if (dp[j+w[i]] < dp[j] + val[i])
            {
                dp[j+w[i]] = dp[j] + val[i];
                if (dp[j+w[i]] > sol)
                    sol = dp[j+w[i]];
            }
    os << sol;
    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n;
    is >> C;
    for (int i = 1; i <= n; ++i)
        is >> w[i] >> val[i];
};