solution

按m为奇数和m为偶数分类来做。

如果m为奇数，那么我们就先对所有物品按价值从小到大排序，然后枚举一下中位数，看枚举的中位数左边最小的个大小和右边最小的个大小之和是不是比要小。如果是，那么就对答案有贡献，否则就没有贡献。
然后问题就在于如何找到一个位置左边最小的个大小和和右边最小的个大小和。我们维护一个大头堆，是中保证这个堆里的元素个数是，当加入一个新元素时，我们就看这个元素是不是比堆顶小，如果是的话就把堆顶弹出来，将这个新元素***去，同时不断维护和。

如果m为偶数，那么同样的方法。但是不能枚举中位数，所以就枚举一下左边的物品，然后二分一下右边的物品y，如果x和y的大小之和和x左边最小的个大小和加上y右边的最小的个大小和比小，那就会对答案产生贡献。否则就没有贡献。

code

/*
* @Author: wxyww
* @Date:   2020-06-10 20:16:56
* @Last Modified time: 2020-06-10 21:25:30
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}

#define pi pair<ll,ll>
pi a[N];

priority_queue<int>q;
int V,n,m;
ll suml[N],sumr[N];
void solve1() {
    ll now = 0;

    for(int i = 1;i <= m / 2;++i) {
        now += a[i].second;
        q.push(a[i].second);
    }
    suml[m / 2] = now;
    for(int i = m / 2 + 1;i <= n;++i) {
        if(!q.empty() && a[i].second < q.top()) {
            now -= q.top();q.pop();
            q.push(a[i].second);
            now += a[i].second;
        }
        suml[i] = now;
    }

    while(!q.empty()) q.pop();
    now = 0;

    for(int i = n;i >= n - m / 2 + 1;--i) {
        now += a[i].second;
        q.push(a[i].second);
    }
    sumr[n - m / 2 + 1] = now;
    for(int i = n - m / 2;i >= 1;--i) {
        if(!q.empty() && a[i].second < q.top()) {
            now -= q.top();
            q.pop();q.push(a[i].second);
            now += a[i].second;
        }
        sumr[i] = now;
    }

    for(int i = n - m / 2;i >= m / 2 + 1;--i) {
        if(suml[i - 1] + sumr[i + 1] + a[i].second <= V) {
            printf("%d\n",a[i].first);return;
        }
    }
}
void solve2() {
    ll now = 0,k = m / 2 - 1;
    for(int i = 1;i <= k;++i) {
        now += a[i].second;q.push(a[i].second);
    }
    suml[k] = now;

    for(int i = k + 1;i <= n;++i) {
        if(!q.empty() && a[i].second < q.top()) {
            now -= q.top();q.pop();
            q.push(a[i].second);now += a[i].second;
        }
        suml[i] = now;
    }
    now = 0;
    while(!q.empty()) q.pop();
    for(int i = n;i >= n - k + 1;--i) {
        now += a[i].second;q.push(a[i].second);
    }
    sumr[n - k + 1] = now;

    for(int i = n - k;i >= 1;--i) {
        if(!q.empty() && a[i].second < q.top()) {
            now -= q.top();q.pop();
            q.push(a[i].second);now += a[i].second;
        }
        sumr[i] = now;
    }
    ll ans = 0;
    for(int i = m / 2;i + m / 2 <= n;++i) {
        int l = i + 1,r = n - m / 2 + 1;
        int ret = 0;
        while(l <= r) {
            int mid = (l + r) >> 1; 
            if(suml[i - 1] + sumr[mid + 1] + a[i].second + a[mid].second <= V) ret = mid,l = mid + 1;
            else r = mid - 1;
        }
        if(ret) {
            ans = max(ans,a[i].first + a[ret].first);
        }
    }
    cout<<ans/2;
}
int main() {
    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 + n + 1);

    if(m & 1) solve1();
    else solve2();
    return 0;
}

/*
10 2 2
1 3
2 3

*/