<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

531. Bonnie and Clyde
Time limit per test: 1.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Bonnie and Clyde are into robbing banks. This time their target is a town called Castle Rock. There are n banks located along Castle Rock's main street; each bank is described by two positive integers xi, wi, where xi represents the distance between the i-th bank and the beginning of the street and wi represents how much money the i-th bank has. The street can be represented as a straight line segment, that's why values of xi can be regarded as the banks' coordinates on some imaginary coordinate axis.

This time Bonnie and Clyde decided to split, they decided to rob two different banks at a time. As robberies aren't exactly rare in Castle Rock, Bonnie and Clyde hope that the police won't see the connection between the two robberies. To decrease the chance of their plan being discovered by the investigation, they decided that the distance between the two robbed banks should be no less than d.

Help Bonnie and Clyde find two such banks, the distance between which is no less than d and the sum of money in which is maximum.

Input
The first input line contains a pair of integers n, d (1 ≤ n ≤ 2 · 105, 1 ≤ d ≤ 108), where n is the number of banks and d is the minimum acceptable distance between the robberies. Then n lines contain descriptions of banks, one per line. Each line contains two integers xi, wi (1 ≤ xi,wi ≤ 108), xi shows how far the i-th bank is from the beginning of the street and wi shows the number of money in the bank. Positions of no two banks coincide. The banks are given in the increasing order of xi.

Output
Print two integer numbers — indicies of the required banks. The banks are numbered starting from 1 in the order in which they follow in the input data. You may print indicies in any order. If there are many solutions, print any of them. If no such pair of banks exists, print "-1 -1" (without quotes).

Example(s)
sample input
sample output
6 3
1 1
3 5
4 8
6 4
10 3
11 2
5 3

<|response|>
1. Abridged Problem Statement
You are given n banks on a line, each at coordinate xi (strictly increasing) and holding wi money. You need to choose two different banks i < j such that xj − xi ≥ d and the sum wi + wj is maximized. Output their 1-based indices (in any order), or "-1 -1" if no valid pair exists.

2. Key Observations
- The banks are sorted by xi, so for each i you can binary-search the smallest j > i with xj ≥ xi + d.
- Among all choices of the left bank up to position i, you only care about the one with maximum w.
- Among all choices of the right bank from position j to n−1, you only care about the one with maximum w.
- Precomputing prefix maxima of w and suffix maxima of w lets you combine these in O(1) per i after a binary search.
- Overall time: O(n log n), which is fine for n up to 2·10^5.

3. Full Solution Approach
a. Read n, d and the array a[i] = (xi, wi) (0-based indexing, already sorted).
b. Build pref[i] = (max weight among a[0..i].w, index of that bank).
   - Scan i from 0 to n−1: pref[i] = max({a[i].w, i}, pref[i−1]) by weight.
c. Build suff[i] = (max weight among a[i..n−1].w, index of that bank).
   - Scan i from n−1 down to 0: suff[i] = max({a[i].w, i}, suff[i+1]) by weight.
d. Initialize answer sum = 0 and ans_pos = (-1, -1).
e. For each i in [0..n−1]:
   - Binary-search j = lower_bound on a for the first index with a[j].x >= a[i].x + d.
   - If no such j, continue.
   - cand = pref[i].weight + suff[j].weight.
   - If cand >= current best, update best and record 1-based indices from pref[i] and suff[j].
f. Print ans_pos.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, d;
vector<pair<int, int>> a;

void read() {
    cin >> n >> d;
    a.resize(n);
    cin >> a;
}

void solve() {
    // Banks come sorted by coordinate x. We pick the left bank i and the right
    // bank j with x[j] - x[i] >= d. For a fixed split point the best left bank
    // is the richest among coordinates <= some value and the best right bank
    // the richest among coordinates >= some value, so we precompute prefix and
    // suffix maxima of (money, index): pref[i] is the richest bank in [0, i],
    // suff[j] the richest in [j, n - 1]. For each i we binary-search the first
    // index j whose coordinate is at least x[i] + d, then pref[i] + suff[j] is
    // a candidate total. We keep the pair achieving the maximum, defaulting to
    // -1 -1 when no valid j exists for any i.

    vector<pair<int, int>> pref(n), suff(n);
    for(int i = 0; i < n; i++) {
        pref[i] = {a[i].second, i};
        if(i > 0) {
            pref[i] = max(pref[i], pref[i - 1]);
        }
    }

    for(int i = n - 1; i >= 0; i--) {
        suff[i] = {a[i].second, i};
        if(i + 1 < n) {
            suff[i] = max(suff[i], suff[i + 1]);
        }
    }

    int ans = 0;
    pair<int, int> ans_pos = {-1, -1};

    for(int i = 0; i < n; i++) {
        auto it = lower_bound(a.begin(), a.end(), make_pair(a[i].first + d, 0));
        if(it == a.end()) {
            continue;
        }

        int j = it - a.begin();
        int cand = pref[i].first + suff[j].first;
        if(cand >= ans) {
            ans = cand;
            ans_pos = {pref[i].second + 1, suff[j].second + 1};
        }
    }

    cout << ans_pos << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation
```python
import sys
import bisect

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    d = int(next(it))
    # Read banks as (x, w), in sorted order by x
    a = [(int(next(it)), int(next(it))) for _ in range(n)]

    # Build prefix max: pref[i] = (max_w so far, index_of_bank)
    pref = [None] * n
    max_w, max_idx = a[0][1], 0
    pref[0] = (max_w, 0)
    for i in range(1, n):
        w = a[i][1]
        if w > max_w:
            max_w, max_idx = w, i
        pref[i] = (max_w, max_idx)

    # Build suffix max: suff[i] = (max_w from i..n-1, index_of_bank)
    suff = [None] * n
    max_w, max_idx = a[n-1][1], n-1
    suff[n-1] = (max_w, max_idx)
    for i in range(n-2, -1, -1):
        w = a[i][1]
        if w >= max_w:  # >= so later index preferred if equal
            max_w, max_idx = w, i
        suff[i] = (max_w, max_idx)

    # Extract x coordinates for binary search
    xs = [x for x, _ in a]

    best_sum = 0
    ans = (-1, -1)

    # For each left bank i
    for i in range(n):
        xi, wi = a[i]
        target = xi + d
        # Find the first j with xj >= xi + d
        j = bisect.bisect_left(xs, target)
        if j == n:
            continue  # no valid right bank
        # Best left in [0..i], best right in [j..n-1]
        wl, idx_l = pref[i]
        wr, idx_r = suff[j]
        total = wl + wr
        if total >= best_sum:
            best_sum = total
            ans = (idx_l + 1, idx_r + 1)  # convert to 1-based

    print(ans[0], ans[1])

if __name__ == "__main__":
    main()
```
