用sum1存储m前半部分的和，sum2存储m后半部分的和。如果m是奇数的话，枚举arr数组，当前位置加上sum1再加上sum2小于等于背包容量，那么这个位置的数就是中位数。如果m是偶数的话，枚举arr数组，当前位置加上sum1再加上sum2小于等于背包容量那么i和i+1的价值和的一半就是中位数，因为i+1的位置在sum2数组中，要想要这个中位数大的话，就尽可能的取sum2中下标靠后的位置，因为sum2的下标越大对应的arr中的val值也就越大（对arr的val升序排序）,所以在满足背包容量的前提下找到sum2中位置靠后的位置

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, m, v;
const int maxn = 1e5 + 7;
struct node {
    ll val;
    ll weight;
}arr[maxn];
priority_queue<ll>q;
ll sum1[maxn];
ll sum2[maxn];
bool cmp(node a, node b) {
    return a.val < b.val;
}
int main()
{
    cin>>v >> n >> m ;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].val >> arr[i].weight;
    }
    sort(arr + 1, arr + n + 1, cmp);
    ll num = m >> 1;
    for (int i = 1; i <= n; i++) {
        q.push(arr[i].weight);
        sum1[i] = sum1[i - 1] + arr[i].weight;
        if (q.size() > num - 1 + (m & 1)) {
            sum1[i] -= q.top();
            q.pop();
        }
    }
    while (!q.empty())q.pop();
    for (int i = n; i >= 1; i--) {
        q.push(arr[i].weight);
        sum2[i] = sum2[i + 1] + arr[i].weight;
        if (q.size() > num) {
            sum2[i] -= q.top();
            q.pop();
        }
    }
    if (m & 1) {
        ll ans = 0;
        for (int i = num + 1; i <= n-num; i++) {
            if (sum1[i - 1] + sum2[i + 1] + arr[i].weight <= v)ans = arr[i].val;
        }
        cout << ans;
    }
    else {
        ll ans = 0;
        for (int i = num; i <= n - num; i++) {
            int l = i;
            int r = n - num + 1;
            while (l < r) {
                int mid = (r + l+1) / 2;
                if (sum1[i - 1] + sum2[mid] + arr[i].weight <= v)l = mid;
                else r = mid-1;
            }
           if(r>i) ans = max(ans, arr[i].val + arr[r].val);
        }
        cout << ans / 2;
    }
}