View Code of Problem 1094

/*
http://blog.csdn.net/liuke19950717
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
struct node
{
	int num,val;
}x[maxn];
int cmp(node a,node b)
{
	if(a.num==b.num)
	{
		return a.val<b.val;
	} 
	return a.num<b.num;
}
int lower[maxn],upper[maxn];
int slove(int n,int m,int s)
{
	memset(lower,-1,sizeof(lower));
	memset(upper,-1,sizeof(upper));
	sort(x,x+n,cmp);
	int mid=m/2,cnta=0,cntb=0;
	priority_queue<int> qa;
	priority_queue<int> qb;
	for(int i=0;i<n;++i)
	{
		lower[i]=(qa.size()==mid)?cnta:inf;
		upper[n-i-1]=(qb.size()==mid)?cntb:inf;
		qa.push(x[i].val);
		qb.push(x[n-i-1].val);
		cnta+=x[i].val;
		cntb+=x[n-i-1].val;
		if(qa.size()>mid)
		{
			cnta-=qa.top();
			qa.pop();
		}
		if(qb.size()>mid)
		{
			cntb-=qb.top();
			qb.pop();
		}
	}
	for(int i=n-1;i>=0;--i)
	{
		if(lower[i]+x[i].val<=s-upper[i])
		{
			return x[i].num;
		}
	}
	return -1;
}
int main()
{
	int n,m,s;
	//freopen("shuju.txt","r",stdin);
	while(~scanf("%d%d%d",&m,&n,&s))
	{
		for(int i=0;i<n;++i)
		{
			scanf("%d%d",&x[i].num,&x[i].val);
		}
		printf("%d\n",slove(n,m,s));	
	}
	return 0;
}