优先队列+二分

题目需要找到中位数最大，那么我们直接按照价值升序排序，再把体重升序排序。
从头把m对半分开，求前m最小和后m最小，如果是奇数最终加上当前这位的体积比v小于等于，直接这一位的价值就是答案。
如果是偶数，这个会复杂一点，因为你无法保证某一次价值大的体重小，但是可以发现，我们是求中间两个取平均，我们已经对这个物品先按价值升序排序，那么我们就在这个合理的区间中可以发现，如果存在符合V的区间，显然我们希望这个区间越靠后面越高兴，所以我们要接一个二分去寻找合理的最大值。
代码写的比较玄乎，码了注释。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) (vv).begin(), (vv).end()
#define endl "\n"
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
pair<ll, ll> a[N];
ll sum1[N], sum2[N]; //前面一半的和，后面一半的和
priority_queue<ll> pq;

int main() {
    ll v = read(), n = read(), m = read();
    for (int i = 1; i <= n; ++i)    a[i].first = read(), a[i].second = read();
    sort(a + 1, a + 1 + n);
    int x = m & 1;    m >>= 1;
    for (int i = 1; i <= n; ++i) {
        pq.push(a[i].second), sum1[i] = sum1[i - 1] + a[i].second;    //求前i个数中m前半段最小值
        if (pq.size() > m - 1 + x)    sum1[i] -= pq.top(), pq.pop();    //去掉最大的
    }
    while (pq.size())    pq.pop();
    for (int i = n; i; --i) {
        pq.push(a[i].second), sum2[i] = sum2[i + 1] + a[i].second;    //后缀和求m后半段最小值
        if (pq.size() > m)    sum2[i] -= pq.top(), pq.pop();
    }
    if (x) { //如果是奇数
        ll ans = 0;
        for (int i = m + 1; i <= n - m; ++i)
            if (sum1[i - 1] + sum2[i + 1] + a[i].second <= v)    ans = a[i].first; //已经按照first升序排过序
        cout << ans << endl;
    }
    else {
        ll ans = 0;
        for (int i = m; i <= n - m; ++i) {
            int l = i + 1, r = n - m + 1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (sum1[i - 1] + sum2[mid] + a[i].second <= v)    l = mid + 1;
                else r = mid - 1;
            }
            if (r > i)    ans = max(ans, 1ll * a[i].first + a[r].first);
        }
        cout << ans / 2 << endl;
    }
    return 0;
}