#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=300020;
const int mxK=14;
const int MOD=1000000007;
const ll INF=1e18;
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
ll N[2], K, M;
pll A[2][mxN];
vector <pll> coor;
ll dp[2][mxN];
ll ans;
bool add_zero;
pll seg1[2][4*mxN];
ll seg2[2][4*mxN];
void upd2(int idx, int s, int e, int pos, int val, int i)
{
if(s==e)
{
seg2[i][idx]=val;
return;
}
int mid=(s+e)/2;
if(pos<=mid) upd2(2*idx, s, mid, pos, val, i);
else upd2(2*idx+1, mid+1, e, pos, val, i);
seg2[i][idx]=max(seg2[i][2*idx], seg2[i][2*idx+1]);
}
int solv2(int idx, int s1, int e1, int s2, int e2, int i)
{
if(s2<=s1 && e1<=e2) return seg2[i][idx];
if(s2>e1 || s1>e2) return 0;
int mid=(s1+e1)/2;
return max(solv2(2*idx, s1, mid, s2, e2, i), solv2(2*idx+1, mid+1, e1, s2, e2, i));
}
void init1(int idx, int s, int e)
{
if(s==e) seg1[0][idx]=pll(A[0][s].fi-2*K*s, A[0][s].se-2*K*s), seg1[1][idx]=pll(A[1][s].fi-2*K*s, A[1][s].se-2*K*s);
else
{
int mid=(s+e)/2;
init1(2*idx, s, mid);
init1(2*idx+1, mid+1, e);
for(int i=0;i<2;i++)
{
seg1[i][idx].fi=max(seg1[i][2*idx].fi, seg1[i][2*idx+1].fi);
seg1[i][idx].se=min(seg1[i][2*idx].se, seg1[i][2*idx+1].se);
}
}
}
pll solv1(int idx, int s1, int e1, int s2, int e2, int i)
{
if(s2<=s1 && e1<=e2) return seg1[i][idx];
if(s2>e1 || s1>e2) return pll(-INF, INF);
int mid=(s1+e1)/2;
pll r1=solv1(2*idx, s1, mid, s2, e2, i), r2=solv1(2*idx+1, mid+1, e1, s2, e2, i);
return pll(max(r1.fi, r2.fi), min(r1.se, r2.se));
}
void input()
{
cin >> N[0] >> N[1] >> K;
for(int i=0;i<N[0];i++) cin >> A[0][i].fi >> A[0][i].se, A[0][i].se--;
for(int i=0;i<N[1];i++) cin >> A[1][i].fi >> A[1][i].se, A[1][i].se--;
sort(A[0], A[0]+N[0]);
sort(A[1], A[1]+N[1]);
if(A[0][0].fi!=0)
{
add_zero=true;
for(int i=N[0];i>=1;i--) A[0][i]=A[0][i-1];
A[0][0]=pii(0, 0);
N[0]++;
}
M=max(N[0], N[1]);
}
void make_coor()
{
for(int i=0;i<2;i++) for(int j=0;j<N[i];j++) coor.emplace_back(i, j);
sort(all(coor), [](pii a, pii b){return A[a.fi][a.se].fi>A[b.fi][b.se].fi;});
}
ll f(int idx, int s, int lim)
{
if(s==N[idx]) return 0;
if(A[idx][s].fi>lim-K) return dp[idx][s];
int e1=lower_bound(A[idx], A[idx]+N[idx], pll(lim-K+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[idx];
int e2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(lim+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[1-idx];
ll res=0;
res=max(res, e1-s+dp[idx][e1]);
res=max(res, e1-s-2+dp[idx][e1-1]);
return res;
}
int bin_search_r1(int idx, int s1, int e1, int s2, int e2, ll val, int i)
{
if(s2>e1 || s1>e2) return e1+1;
if(s2<=s1 && e1<=e2)
{
if(seg1[i][idx].fi<=val && seg1[i][idx].se>=val) return e1+1;
if(s1==e1) return s1;
}
int mid=(s1+e1)/2;
if(e2<=mid) return bin_search1(2*idx, s1, mid, s2, e2, val, i);
if(s2>mid) return bin_search1(2*idx+1, mid+1, e1, s2, e2, val, i);
int res1=bin_search1(2*idx, s1, mid, s2, e2, val, i);
if(res1!=mid+1) return res1;
return bin_search1(2*idx+1, mid+1, e1, s2, e2, val, i);
}
int bin_search1(int idx, ll val, int s, int e)
{
pll tmp=solv1(1, 0, M-1, s, e, idx);
if(val<=tmp.se && val>=tmp.fi) return e;
return bin_search_r1(1, 0, M-1, s, e, val, idx)-1;
}
void mx(ll &a, ll b){a=max(a, b);}
int main()
{
gibon
input();
make_coor();
init1(1, 0, M-1);
upd2(1, 0, M, N[0], 2*N[0], 0);
upd2(1, 0, M, N[1], 2*N[1], 1);
for(auto [idx, now] : coor)
{
ll nc=A[idx][now].fi;
dp[idx][now]=dp[idx][now+1]+1;
ll s1=now, s2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(nc+K, nc+K), [](pll a, pll b){return a.se<b.se;})-A[1-idx];
if(s2==N[1-idx])
{
upd2(1, 0, M, now, dp[idx][now]+2*now, idx);
continue;
}
if(A[1-idx][s2].fi>nc+K)
{
mx(dp[idx][now], f(1-idx, s2, A[idx][now].se)+1);
upd2(1, 0, M, now, dp[idx][now]+2*now, idx);
continue;
}
ll c1=bin_search1(idx, nc-2*K*s1, s1, N[idx]-1), c2=bin_search1(1-idx, nc+K-2*K*s2, s2, N[1-idx]-1);
/*
ll c1=s1, c2=s2;
while(c1+1<N[idx] && nc+2*K*(c1+1-s1)<=A[idx][c1+1].se && nc+2*K*(c1+1-s1)>=A[idx][c1+1].fi) c1++;
while(c2+1<N[1-idx] && nc+2*K*(c2+1-s2)+K<=A[1-idx][c2+1].se && nc+2*K*(c2+1-s2)+K>=A[1-idx][c2+1].fi) c2++;
*/
if(c2-s2<c1-s1-1) c1=c2-s2+s1+1;
if(c2-s2>c1-s1) c2=c1-s1+s2;
if(c2-s2==c1-s1)
{
mx(dp[idx][now], solv2(1, 0, M, s1+1, c1+1, idx)-2*s1-1);
if(s2<=c2-1) mx(dp[idx][now], solv2(1, 0, M, s2+1, c2, 1-idx)-2*s2);
/*
for(int i=s1;i<=c1;i++) mx(dp[idx][now], dp[idx][i+1]+2*(i-s1)+1);
for(int i=s2;i<c2;i++) mx(dp[idx][now], dp[1-idx][i+1]+2*(i-s2)+2);
*/
mx(dp[idx][now], f(1-idx, c2+1, A[idx][c1].se)+c1-s1+c2-s2+2);
ll nxt=nc+2*K*(c1-s1+1);
if(c1+1<N[idx] && nxt<A[idx][c1+1].fi) mx(dp[idx][now], f(idx, c1+1, A[1-idx][c2].se)+2*(c1-s1+1));
}
else
{
if(s1<=c1-1) mx(dp[idx][now], solv2(1, 0, M, s1+1, c1, idx)-2*s1-1);
mx(dp[idx][now], solv2(1, 0, M, s2+1, c2+1, 1-idx)-2*s2);
/*
for(int i=s1;i<c1;i++) mx(dp[idx][now], dp[idx][i+1]+2*(i-s1)+1);
for(int i=s2;i<=c2;i++) mx(dp[idx][now], dp[1-idx][i+1]+2*(i-s2)+2);
*/
mx(dp[idx][now], f(idx, c1+1, A[1-idx][c2].se)+2*(c1-s1)+1);
ll nxt=nc+2*K*(c1-s1)+K;
if(c2+1<N[1-idx] && nxt<A[1-idx][c2+1].fi) mx(dp[idx][now], f(1-idx, c2+1, A[idx][c1].se)+2*(c1-s1)+1);
}
upd2(1, 0, M, now, dp[idx][now]+2*now, idx);
}
cout << dp[0][0]-(add_zero ? 1 : 0);
}
/*
3 3 10
1 30
31 60
61 90
15 45
45 90
90 120
*/
Compilation message
Main.cpp: In function 'll f(int, int, int)':
Main.cpp:96:9: warning: unused variable 'e2' [-Wunused-variable]
96 | int e2=lower_bound(A[1-idx], A[1-idx]+N[1-idx], pll(lim+1, 0), [](pll a, pll b){return a.fi<b.fi;})-A[1-idx];
| ^~
Main.cpp: In function 'int bin_search_r1(int, int, int, int, int, ll, int)':
Main.cpp:111:24: error: 'bin_search1' was not declared in this scope; did you mean 'bin_search_r1'?
111 | if(e2<=mid) return bin_search1(2*idx, s1, mid, s2, e2, val, i);
| ^~~~~~~~~~~
| bin_search_r1
Main.cpp:112:24: error: 'bin_search1' was not declared in this scope; did you mean 'bin_search_r1'?
112 | if(s2>mid) return bin_search1(2*idx+1, mid+1, e1, s2, e2, val, i);
| ^~~~~~~~~~~
| bin_search_r1
Main.cpp:113:14: error: 'bin_search1' was not declared in this scope; did you mean 'bin_search_r1'?
113 | int res1=bin_search1(2*idx, s1, mid, s2, e2, val, i);
| ^~~~~~~~~~~
| bin_search_r1
