Untitled

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int tc;
int ret;

int N, S, K;
vector<vector<int>> acorns;

class acorns_comparator
{
public:
    bool operator() (const vector<int> &v1, const vector<int> &v2)
    {
        return v1[0] < v2[0];
    }
};

void read_input()
{
    cin >> N >> S >> K;

    acorns.assign(N, vector<int>(2));

    for (int i = 0; i < N; ++i) {
        cin >> acorns[i][0] >> acorns[i][1];
    }
}

void solve()
{
    sort(acorns.begin(), acorns.end(), acorns_comparator());

    int left = 0;
    int right = N - 1;
    int mid;
    int left_start, right_start;
    vector<int> sums;

    sums.assign(N, 0);
    left_start = right_start = -1;

    while (left <= right) {
        mid = (left + right) / 2;
        if (acorns[mid][0] < S) {
            left_start = mid;
            left = mid + 1;
        } else {
            right_start = mid;
            right = mid - 1;
        } 
    }
    if (left_start == -1) {
        /*
         * all 
         */
        for (int i = 0; i < N; ++i) {
            if (acorns[i][0] - S <= K) {
                ret += acorns[i][1];
            } else {
                break;
            }
        }
    } else if (right_start == -1) {
        for (int i = N - 1; i >= 0; i--) {
            if (S - acorns[i][0] <= K) {
                ret += acorns[i][1];
            } else {
                break;
            }
        }
    } else {
        for (int i = right_start; i < N; i++) {
            sums[i] = acorns[i][1] + (i > right_start ? sums[i - 1] : 0);
        }
        for (int i = left_start; i >= 0; i--) {
            sums[i] = acorns[i][1] + (i < left_start ? sums[i + 1] : 0);
        }

        for (int i = left_start; i >= 0; i--) {
            int hld = S - acorns[i][0];
            if (hld > K) break;

            int ld = hld * 2;
            int rd = K - ld;

            int lsum = sums[i];
            int rsum = 0;

            if (rd > 0) {
                left = right_start;
                right = N - 1;
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (acorns[mid][0] - S <= rd) {
                        found = mid;
                        rsum = sums[found];
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            ret = max(ret, lsum + rsum);
        }
    }

}

void print_output()
{
    cout << "#" << tc << " " << ret << endl;
}

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false);

    int T;
    cin >> T;
    tc = 1;
    while (T) {
        read_input();
        solve();
        print_output();
        tc++;
        T--;
    }
    return 0;
}