View Code of Problem 1093

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <vector>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;


#define pb push_back
#define mp make_pair
#define fillchar(a, x) memset(a, x, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r


typedef long long LL;
typedef pair<int, int > PII;
typedef unsigned long long uLL;

template<typename T>
void print(T* p, T* q, string Gap = " ") {
	int d = p < q ? 1 : -1;
	while(p != q) {
		cout << *p;
		p += d;
		if(p != q) cout << Gap;
	}
	cout << endl;
}
template<typename T>
void print(const T &a, string bes = "") {
	int len = bes.length();
	if(len >= 2)cout << bes[0] << a << bes[1] << endl;
	else cout << a << endl;
}

const int INF = 0x3f3f3f3f;
const int MAXM = 2e5;
const int MAXN = 1e5 + 5;
int N, C, F;
struct o {
	int g, f;
	int id;
} OL[MAXN], OR[MAXN];

bool cmp1(const o &p, const o &q) {
	return p.f < q.f;
}

bool cmp2 (const o &p, const o &q) {
	return p.g < q.g;
}

int CA(int mid) {
	int sum = OL[mid].f;
	int l = 0, r = 0;
	int Z = N / 2;
	for(int i = 0; i < C; i ++) {
		if(l < Z && OR[i].id < mid && sum + OR[i].f <= F) {
			sum += OR[i].f;
			l ++;
		}
		if(r < Z && OR[i].id > mid && sum + OR[i].f <= F) {
			sum += OR[i].f;
			r ++;
		}
	}
	if(l < Z && r < Z) {
		return -1;
	} else if(l < Z) {
		return 1;
	} else if(r < Z) {
		return 2;
	} else {
		return 3;
	}
}
int main() {
	while(~scanf("%d%d%d", &N, &C, &F)) {
		LL Max = 0;
		for(int i = 0; i < C; i ++) {
			scanf("%d%d", &OL[i].g, &OL[i].f);
		}
		sort(OL, OL + C, cmp2);
		for(int i = 0; i < C; i ++) {
			OL[i].id = i;
			OR[i].f = OL[i].f;
			OR[i].g = OL[i].g;
			OR[i].id = i;
		}
		sort(OR, OR + C, cmp1);
		int lb = -1, ub = C - 1;
		int ret = -1;
		while(ub - lb > 1) {
			int mid = (ub + lb) >> 1;
			int Z = CA(mid);
			if(Z == 1) {
				lb = mid;
			} else if(Z == 2) {
				ub = mid;
			} else if(Z == -1) {
				ret = -1;
				break;
			} else {
				ret = OL[mid].g;
				lb = mid;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}