Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你
当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入描述:
第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量
接下来n行，每行两个数ai，bi，分别代表物品价值以及大小
n ≤ 1e5, 1 ≤ m ≤ n, ai ≤ 1e9, v ≤ 1e9, bi ≤ v

输出描述:
仅一行，代表最大的中位数
示例1
输入
20 5 3
3 5
5 6
8 7
10 6
15 10
输出
8

#include<bits/stdc++.h>
using namespace std;typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define gc (c=getchar())
int read()
{char c;while(gc<'0');int x=c-'0';while(gc>='0')x=x*10+c-'0';return x;
}
const int N=5e6+5,U=1<<15;
int cnt[U];
int n,a[N],b[N],qa[N],qb[N];
int idb[N];
bool mark[N];
s64 s1[N],s2[N];int q1[N];
void get(int q[],int a[])
{rep(i,0,U-1)cnt[i]=0;rep(i,1,n)++cnt[a[i]%U];rep(i,1,U-1)cnt[i]+=cnt[i-1];per(i,n,1)q1[cnt[a[i]%U]--]=i;rep(i,0,U-1)cnt[i]=0;rep(i,1,n)++cnt[a[i]/U];rep(i,1,U-1)cnt[i]+=cnt[i-1];per(i,n,1)q[cnt[a[q1[i]]/U]--]=q1[i];
}
s64 sum;int tail;
void del(int x)
{mark[x]=1;if(x<=tail){sum-=b[qb[x]];while(++tail,mark[tail]);sum+=b[qb[tail]];}
} int k;
void init_s()
{rep(i,1,n)idb[qb[i]]=i;sum=0;rep(i,1,k)sum+=b[qb[i]];s64 sum0=sum;tail=k;s2[1]=sum;rep(i,2,n-k+1){del(idb[qa[i-1]]);s2[i]=sum;}sum=sum0;tail=k;rep(i,1,n)mark[i]=0;s1[n]=sum;per(i,n-1,k){del(idb[qa[i+1]]);s1[i]=sum;}
}int main()
{//freopen("1.in","r",stdin);int v=read();n=read();int m=read();rep(i,1,n){a[i]=read();b[i]=read();}get(qa,a);get(qb,b);k=m/2;	init_s();if(m%2){per(i,n-k,1)if(s1[i-1]+b[qa[i]]+s2[i+1]<=v){cout<<a[qa[i]];break;}}else{per(i,n-k,1)if(s1[i]+s2[i+1]<=v){cout<<(a[qa[i]]+a[qa[i+1]])/2;break;	}}
}