When Takahashi chooses positive integers \(S\) and \(L\) to place a basket, he gets an apple falling at coordinate \(X_i\) at time \(T_i\) if and only if \(\max(T_i-D+1,1)\leq S \leq T_i\) and \(\max(X_i-W+1,1)\leq L\leq X_i\). Thus, the problem can be rephrased as follows.

There is an infinite \(tx\) coordinate plane. Initially, each lattice point \((t,x)\) with \(t>0\) and \(x>0\) has an integer \(0\) written on it.
(A lattice point is a point whose \(t\) and \(x\) coordinates are both integers.)
We perform \(N\) operations. In the \(i\)-th operation, we add \(1\) to the number written on each lattice point \((t, x)\) such that \(\max(T_i-D+1,1)\leq t \leq T_i\) and \(\max(X_i-W+1,1)\leq x\leq X_i\).
Find the maximum number written on a lattice point within the range of \(t>0\) and \(x>0\).

In this problem, the number written on a lattice point after the \(N\) operations corresponds to the number of apples that he can acquire if he chooses \(S\) and \(L\) in the original problem.

Trying to solve this problem in a naive way costs \(O(NDW)\) time, which is hard to finish in the time limit.
This problem can be solved fast using lazy segment tree.
Here, note that we only have to consider the lattice points \((t,x)\) such that \(1\leq t\leq \max(T_i)\) and \(1\leq x\leq \max(X_i)\).

First, we consider how to find the maximum value written on \((1,x)\) \((1\leq x\leq \max(X_i))\).
This can be done as follows.
First, prepare an array \(A=(A_1,A_2,\ldots,A_{\max(X_i)})\), all initialized with \(0\).
Then, for each operation such that \(\max(T_i-D+1,1)\leq 1 \leq T_i\), i.e. \(T_i\leq D\), add \(1\) to \(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\). Finally, find the maximum value in \(A\).

Next, for \(t_0\geq 2\), we consider how to find the maximum value written on \((t_0,x)\) \((1\leq x\leq 2\times 10^5)\). This can be found by reusing the array for \(t=t_0-1\) and modify the changes. There are two types of possible updates:

• For an operation such that \(t-1<\max(T_i-D+1,1)\leq t\), i.e. \(T_i=t+D-1\), add \(1\) to \(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\).

• For an operation such that \(t-1\leq T_i< t\), i.e. \(T_i=t-1\), subtract \(1\) from \(A_x\) \((\max(X_i-W+1,1)\leq x\leq X_i)\).

By finding the maximum value in \(A\), one can find the maximum value among the numbers written on \((t_0,x)\) \((1\leq x)\).

The answer can be obtained as the maximum value of “the maximum value among the numbers written on \((t_0,x)\) \((1\leq x)\)”.

Now, the following two operations are to be performed against the array \(A\):

• Add a specific value to a specified range of the array. (Segment addition)
• Find the maximum value within a specified range (this time, only the entire array) of the array. (Segment maximum retrieval)

A segment tree supports both of these operations in \(O(\log |A|)\) time (where \(|A|\) is the length of \(A\) \((=\max(X_i))\)). The number of segment additions is at most twice per each operation, for a total of at most \(2N\); the retrieval of the maximum value is performed only at most \(\max(T_i)\) time. Thus, the overall complexity is \(O(N+\max(T_i))\log(\max(X_i)))\), which is fast enough.

Therefore, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

const int Tmax=(int)2e+5;
const int Xmax=(int)2e+5;

struct S {
    int x;
};

struct F {
    int x;
};

S op(S l, S r) { return S{max(l.x,r.x)}; }

S e() { return S{0}; }

S mapping(F l, S r) { return S{l.x+r.x}; }

F composition(F l, F r) { return F{l.x+r.x}; }

F id() { return F{0}; }

int main(void) {
	int n,d,w,t,x,ans=0;
	vector<pair<int,int> >q[Tmax+1];
	cin>>n>>d>>w;
	for(int i=0;i<n;i++){
		cin>>t>>x;
		q[max(t-d,0)].push_back({x,1});
		q[t].push_back({x,-1});
	}
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(Xmax);
    for(int i=0;i<Tmax;i++){
        int sz=q[i].size();
        for(int j=0;j<sz;j++){
            seg.apply(max(0,q[i][j].first-w),q[i][j].first,F{q[i][j].second});
        }
        ans=max(ans,seg.prod(0,Xmax).x);
    }
	cout<<ans<<endl;
	return 0;
}