#include <bits/stdc++.h>

using namespace std;
int i, j,n, g, k, values[5002], weights[5002], keep1[10002];
int main()
{ freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

     cin >> n >> g;
     for(i = 0; i< n; i++)
    cin >> weights[i] >> values[i];
    int sol = 0;
    for(i = 0; i< n; i++)
        for(j = g - weights[i]; j >= 0; j-- )
      if( keep1[j + weights[i]] < keep1[j] + values[i] )
            {
                keep1[j+weights[i]] = keep1[j] + values[i];
                if( keep1[j+weights[i]] > sol)
                    sol = keep1[j+weights[i]];
            }

    cout << sol;
    return 0;
}