#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class FibonacciKnapsack { public:
long long maximalCost(vector <string> items, string C_)
{
LL C;
stringstream(C_) >> C;
vector< pair<LL,LL> > wp;
for(int i=0; i<items.size(); ++i) {
LL W, P;
stringstream(items[i]) >> W >> P;
wp.push_back( make_pair(W,P) );
}
sort( wp.begin(), wp.end() );
LL lW = 0, lP = 0;
for(int i=0; i<wp.size(); ++i)
lW += wp[i].first, lP += wp[i].second;
best = 0;
rec( lW, lP, wp, wp.size()-1, C, 0 );
return best;
}
LL best;
void rec( LL lW, LL lP, vector< pair<LL,LL> >& wp, int i, LL w, LL cP )
{
if( lW <= w )
best = max(best, lP+cP);
if( lP+cP <= best )
return;
for(int k=i; k>=0 && wp[k].first==wp[i].first; --k)
{
lW -= wp[k].first;
lP -= wp[k].second;
if( w >= 0 )
rec(lW, lP, wp, k-1, w, cP);
w -= wp[k].first;
cP += wp[k].second;
}
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, FibonacciKnapsack().maximalCost(items, C));}
int main(){
CASE(0)
string items_[] = {"5 555", "8 195", "13 651"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "15";
long long _ = 750LL;
END
CASE(1)
string items_[] = {"5 555", "8 195", "13 751"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "15";
long long _ = 751LL;
END
CASE(2)
string items_[] = {"55 1562", "5 814", "55 1962", "8 996", "2 716", "34 1792"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "94";
long long _ = 4568LL;
END
CASE(3)
string items_[] = {"13 89"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "1";
long long _ = 0LL;
END
CASE(4)
string items_[] = {"27777890035288 9419696870097445",
"53316291173 6312623457097563",
"165580141 8848283653257131"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "27777900000000";
long long _ = 15160907110354694LL;
END
CASE(5)
string items_[] = {"89 90", "55 54", "55 54", "34 35", "34 35", "34 35", "34 35", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "21 23", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "13 14", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10", "8 10"};
vector <string> items(items_, items_+sizeof(items_)/sizeof(*items_));
string C = "200";
long long _ = 241LL;
END
}
// END CUT HERE