注意，答案直接向下取整！！！

被这个玩意儿坑了，好惨啊。。。

关于这道题，我们先来看看m是奇数怎么做。

很明显，我们可以考虑枚举中位数，然后判断其是否可行即可。这样，我们先对所有物品按价值从小到大排序。

那么，如果一个物品可以作为中位数，当前仅当存在一种方案，从这个物品的左边选个物品，再从它右边选个物品，他们的容积和加上该物品的容积小于等于背包容积v。那么，我们明显只需要贪心去取，每次取最小的几个即可。

那么，我们设表示，我们从i号点左/右取个物品的最小容积和。

对于这个，我们直接开个优先队列，使得优先队列的元素是当前最小的个元素即可。

那么，枚举i时，我们只需要判断下是否小于等于v，即可。

那么，m为偶数怎么做呢？

我们发现，其实，我们可以把它看做我们从左边的中位数的左边拿个物品，再从右边的中位数的右边拿个物品，所以，对于这个情况，我们参考m为奇数的时候，设表示从i的左边/右边拿个物品的最小容积和。

那么，我们就可以开始枚举了，但是，现在的中位数有两个，我们不可能同时枚举两个，那样复杂度会变成n^2,明显是不行的。那么，我们考虑枚举其中一个，然后另一个贪心来弄。我们考虑枚举右边的中位数,编号设为i，那么，其实我们就是要求一个最大的j，使得j<i,并且

那么，很明显，因为对于每个点j，它的是一个常数，我们只需要找到最大的那个符合条件的j即可，直接上个单调栈，然后在单调栈上二分一下就好了。
（我太菜了，打的单调队列qwq）

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
#define int long long
struct node{
    int a,b;
}t[N];
int w[N][2],val[N];
priority_queue<int>sp;
inline bool kkk(node x,node y){
    return x.a<y.a;
}
int que[N],l=1,r;
signed main(){
    int v,n,m;
    scanf("%lld%lld%lld",&v,&n,&m);
    //枚举算答案，贪心判可行
    for(int i=1;i<=n;++i)scanf("%lld%lld",&t[i].a,&t[i].b);
    sort(t+1,t+n+1,kkk);
    int s,sum=0;
    if(m&1)s=(m-1)/2;
    else s=(m-2)/2;
    for(int i=1;i<=n;++i){
        w[i][0]=sum;
        if(sp.size()<s)sp.push(t[i].b),sum+=t[i].b;
        else{
            if(!s)continue;
            if(sp.top()>t[i].b)sum-=(sp.top()-t[i].b),sp.pop(),sp.push(t[i].b);
        }
    }
    while(!sp.empty())sp.pop();
    sum=0;
    for(int i=n;i;--i){
        w[i][1]=sum;
        if(sp.size()<s)sp.push(t[i].b),sum+=t[i].b;
        else{
            if(!s)continue;
            if(sp.top()>t[i].b)sum-=(sp.top()-t[i].b),sp.pop(),sp.push(t[i].b);
        }
    }
    if(m&1){
        int ans=0;
        for(int i=s+1;i<=n-s;++i){
            int res=w[i][0]+w[i][1]+t[i].b;
            if(res<=v)ans=t[i].a;
        }
        printf("%lld",ans);
        system("pause");
        return 0;
    }else{
        int ans=0;
        for(int i=s+1;i<=n-s;++i){//枚举右边的中位数
            int now=t[i].b+w[i][1];val[i]=t[i].b+w[i][0];
            int L=1,R=(r-l+1),res=0;
            while(L<=R){
                int mid=(L+R)>>1;
                if(now+val[que[l+mid-1]]<=v){
                    res=que[l+mid-1],L=mid+1;
                }else{
                    R=mid-1;
                }
            }
            if(res)ans=max(ans,t[i].a+t[res].a);
            while(l<=r&&val[que[r]]>=val[i])--r;
            que[++r]=i;
        }
        ans/=2;
        printf("%lld",ans);
    }
    system("pause");
    return 0;
}