<|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 arrays x[i], w[i] (0-based indexing).  
b. Build an array pref[i] = (max weight among w[0..i], index of that bank).  
   - Scan i from 0 to n−1:  
     pref[i] = (w[i], i)  
     if i>0 and pref[i−1].weight > pref[i].weight, copy pref[i−1].  
c. Build an array suff[i] = (max weight among w[i..n−1], index of that bank).  
   - Scan i from n−1 down to 0:  
     suff[i] = (w[i], i)  
     if i<n−1 and suff[i+1].weight ≥ suff[i].weight, copy suff[i+1].  
   (Using ≥ in the suffix ensures that, in ties, the rightmost index is chosen.)  
d. Extract the x-coordinates into a separate array X for binary search.  
e. Initialize best_sum = −1 and answer indices ans = (−1,−1).  
f. For each i in [0..n−1]:  
   - Let target = x[i] + d.  
   - Binary-search j = lower_bound(X, target). If j==n, continue.  
   - Let (wl, il) = pref[i], (wr, ir) = suff[j].  
   - If wl + wr > best_sum, update best_sum = wl + wr, ans = (il+1, ir+1).  
g. Print ans (or “-1 -1” if best_sum<0).

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    long long d;
    cin >> n >> d;

    vector<long long> x(n), w(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> w[i];
    }
    // Prepare for binary search on x
    vector<long long> X = x;

    // Build prefix maxima: prefW[i] = best weight up to i, prefI[i] = its index
    vector<long long> prefW(n);
    vector<int> prefI(n);
    prefW[0] = w[0];
    prefI[0] = 0;
    for (int i = 1; i < n; i++) {
        if (w[i] > prefW[i-1]) {
            prefW[i] = w[i];
            prefI[i] = i;
        } else {
            prefW[i] = prefW[i-1];
            prefI[i] = prefI[i-1];
        }
    }

    // Build suffix maxima: suffW[i] = best weight from i..n-1, suffI[i] = its index
    vector<long long> suffW(n);
    vector<int> suffI(n);
    suffW[n-1] = w[n-1];
    suffI[n-1] = n-1;
    for (int i = n-2; i >= 0; i--) {
        // Use >= so we pick the rightmost bank in case of ties
        if (w[i] >= suffW[i+1]) {
            suffW[i] = w[i];
            suffI[i] = i;
        } else {
            suffW[i] = suffW[i+1];
            suffI[i] = suffI[i+1];
        }
    }

    long long bestSum = -1;
    pair<int,int> answer = {-1, -1};

    // For each bank i as the left robbery
    for (int i = 0; i < n; i++) {
        long long needed = x[i] + d;
        // Find the first j with X[j] >= needed
        int j = int(lower_bound(X.begin(), X.end(), needed) - X.begin());
        if (j == n) continue; // no valid partner to the right

        long long wl = prefW[i];
        int il = prefI[i];
        long long wr = suffW[j];
        int ir = suffI[j];

        if (wl + wr > bestSum) {
            bestSum = wl + wr;
            // store 1-based indices
            answer = {il + 1, ir + 1};
        }
    }

    // If bestSum was never updated, answer remains (-1,-1)
    cout << answer.first << " " << answer.second << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
import bisect

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    d = int(next(it))

    # Read banks: lists of x and w
    x = [0]*n
    w = [0]*n
    for i in range(n):
        x[i] = int(next(it))
        w[i] = int(next(it))

    # Build prefix maxima
    prefW = [0]*n
    prefI = [0]*n
    prefW[0] = w[0]
    prefI[0] = 0
    for i in range(1, n):
        if w[i] > prefW[i-1]:
            prefW[i] = w[i]
            prefI[i] = i
        else:
            prefW[i] = prefW[i-1]
            prefI[i] = prefI[i-1]

    # Build suffix maxima
    suffW = [0]*n
    suffI = [0]*n
    suffW[n-1] = w[n-1]
    suffI[n-1] = n-1
    for i in range(n-2, -1, -1):
        # >= so we take the rightmost in ties
        if w[i] >= suffW[i+1]:
            suffW[i] = w[i]
            suffI[i] = i
        else:
            suffW[i] = suffW[i+1]
            suffI[i] = suffI[i+1]

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

    # For each left index i
    for i in range(n):
        target = x[i] + d
        j = bisect.bisect_left(x, target)
        if j == n:
            continue
        wl, il = prefW[i], prefI[i]
        wr, ir = suffW[j], suffI[j]
        total = wl + wr
        if total > best_sum:
            best_sum = total
            ans = (il+1, ir+1)  # convert to 1-based

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

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