#include <bits/stdc++.h>

using namespace std;

#define ALL(x) (x).begin(), (x).end()

template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); }
template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); }

#ifdef LOCAL
const bool debug = true;
#else
const bool debug = false;
#define cerr if (true) {} else cout
#endif

//#define int long long
//#define double long double

//const int INF = 1e18;
//const int mod = 1e9 + 7;

const int nax = 16;

bool czy[nax][1 << nax];
bool  dp[nax][1 << nax];

int ck[1000000];
vector<int> plecaki;

int len[100], cost[100];

int pot(int n, int k) {
	int res = 1;
	while (k--) {
		res *= n;
	}
	return res;
}

vector<int> submaski[1 << nax];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int h, t;
    /*cin >> h >> t;
    
    for (int i = 0; i < h; i++) {
		cin >> ck[i];
	}
	
	for (int i = 1; i <= t; i++) {
		int dl = 0;
		for (int j = 0; j <= h; j++) {
			if (ck[j] >= i) {
				dl++;
			} else {
				plecaki.push_back(dl);
				dl = 0;
			}
		}
	}*/
	
	t = 16;
	while ((int)plecaki.size() < 20) plecaki.push_back(0);
	
	sort(ALL(plecaki));
	reverse(ALL(plecaki));
	plecaki.resize(t);
	
	if (debug) {
		cerr << "plecak: ";
		for (int i : plecaki) cerr << i << " ";
		cerr << "\n";
	}
	
	/*for (int i = 0; i < t; i++) {
		cin >> len[i] >> cost[i];
	}*/
	cerr << "xd" << endl;
	
	for (int i = 0; i < t; i++) {
		czy[i][0] = true;
		for (int mask = 0; mask < (1 << t); mask++) {
			int len_sum = 0;
			for (int j = 0; j < t; j++) {
				if (mask & (1 << j)) {
					len_sum += len[j];
				}
			}
			if (len_sum <= plecaki[i]) {
				czy[i][mask] = true;
				cerr << "czy " << i << " " << mask << endl;
			}
		}
	}
	cerr << "xd2" << endl;
	
	cerr << "pot " << pot(3, t) << endl;
	for (int _mask3 = 0; _mask3 < pot(3, t); _mask3++) {
		int mask = 0, mask2 = 0, mask3 = _mask3;
		for (int i = 0; i < t; i++) {
			int x = mask3 % 3;
			mask *= 2;
			mask2 *= 2;
			if (x == 1) mask++;
			if (x >= 1) mask2++;
			mask3 /= 3;
		}
		submaski[mask2].push_back(mask);
		cerr << "sub " << mask2 << " " << mask << endl;
	}
	//t = 7;
	if (debug) {
		cerr << "submaski ";
		for (int i : submaski[3]) cerr << i << " ";
		cerr << endl;
	}
	cerr << "xd3" << endl;
	
	for (int mask = 0; mask < (1 << t); mask++) {
		dp[0][mask] = czy[0][mask];
		cerr << "dp " << 0 << " " << mask << "    " << dp[0][mask] << endl;
	}
	
	for (int i = 1; i < t; i++) {
		dp[i][0] = true;
		
		for (int mask = 0; mask < (1 << t); mask++) {
			for (int submask : submaski[mask]) {
				dp[i][mask] |= dp[i - 1][submask] && czy[i][mask ^ submask];
			}
			cerr << "dp " << i << " " << mask << "    " << dp[i][mask] << endl;
		}
	}
	
	long long res = 0;
	for (int mask = 0; mask < (1 << t); mask++) {
		if (dp[t - 1][mask]) {
			long long cur = 0;
			for (int i = 0; i < t; i++) {
				if (mask & (1 << i)) {
					cur += cost[i];
				}
			}
			maxi(res, cur);
		}
	}
	
	cout << res << "\n";
    
    return 0;
}/*
3 4
2 1 2
3 2
1 1
1 2
1 3
* 
4 7
2 2 1 1
3 1
1 1
1 4
1 1
2 4
2 2
2 1
*/