#include <bits/stdc++.h>

using namespace std;

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

int w[5001], p[5001], dp[10001];
int n, g;


int main (void)
{
    f >> n >> g;

    for (int i = 0; i < n; i++)
        cin >> w[i] >> p[i];

    for (int i = 0; i < n; i++)
        for (int j = g; j >= w[i]; j--)
            dp[j] = max (dp[j], p[i] + dp[j - w[i]]);
  
    g << dp[g];
}