#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, d; cin >> n >> m >> d;
vector <int> P(n), Q(n), R(m), S(m);
for ( int i = 0; i < n; i++ ){
cin >> P[i] >> Q[i];
}
for ( int i = 0; i < m; i++ ){
cin >> R[i] >> S[i];
}
{ // sorting
vector <int> p_(m);
iota(all(p_), 0);
sort(all(p_), [&](int &u, int &v){
return R[u] < R[v];
});
auto _R = R, _S = S;
for ( int i = 0; i < m; i++ ){
R[i] = _R[p_[i]];
S[i] = _S[p_[i]];
}
p_ = vector <int> (n);
iota(all(p_), 0);
sort(all(p_), [&](int &u, int &v){
return P[u] < P[v];
});
auto _P = P, _Q = Q;
for ( int i = 0; i < n; i++ ){
P[i] = _P[p_[i]];
Q[i] = _Q[p_[i]];
}
}
if ( m <= 8 ){ // subtask #1
vector <int> v(d * 2, -1), has(d * 2), tv(d * 2, -1);
vector <vector<int>> er(d * 2);
for ( int i = 0; i < n; i++ ){
tv[Q[i]] = true;
has[Q[i]] = true;
}
for ( int i = 0; i < m; i++ ){
chmax(v[S[i]], R[i]);
has[S[i]] = true;
}
for ( int i = 0; i < d * 2; i++ ){
if ( v[i] != -1 ){
er[v[i]].pb(i);
}
}
int opt = 1e9, mx = *max_element(all(P)), _ip = 0, _ir = 0;
for ( int l = 0; l < d; l++ ){
while ( _ip < n && P[_ip] < l ){
chmax(mx, P[_ip] + d);
_ip++;
}
while ( _ir < m && R[_ir] < l ){
auto flag = chmax(v[S[_ir]], R[_ir] + d);
if ( flag > 0 ){
er[R[_ir] + d].pb(S[_ir]);
}
_ir++;
}
set <int> st;
vector <int> lf(d * 2, -1), rg(d * 2, -1);
for ( int i = 1; i < d * 2; i++ ){
if ( has[i - 1] > 0 ){
lf[i] = i - 1;
} else{
lf[i] = lf[i - 1];
}
}
for ( int i = (d - 1) * 2; i >= 0; i-- ){
if ( has[i + 1] ){
rg[i] = i + 1;
} else{
rg[i] = rg[i + 1];
}
}
int maxDiff = 0;
for ( int i = 0; i < d * 2; i++ ){
if ( has[i] > 0 ){
st.insert(i);
if ( rg[i] != -1 ){
chmax(maxDiff, rg[i] - i);
}
}
}
auto del = [&](int x){
st.erase(x);
if ( lf[x] != -1 ){
rg[lf[x]] = rg[x];
}
if ( rg[x] != -1 ){
lf[rg[x]] = lf[x];
}
if ( lf[x] != -1 && rg[x] != -1 ){
chmax(maxDiff, rg[x] - lf[x]);
}
};
for ( int r = l; r <= l + d; r++ ){
for ( auto &y: er[r] ){
if ( tv[y] < 1 ){
del(y);
}
}
if ( r >= mx ){
chmin(opt, (r - l + 1) * min(*st.rbegin() - *st.begin() + 1, d - maxDiff + 1));
/*cout << l << " " << r << " -> " << opt << " maxDiff : " << maxDiff << ln;
for ( auto &u: st ) cout << u << ' ';
cout << ln;
opt = 1e9;*/
}
}
}
cout << opt << ln;
return 0;
}
vector <ar<int,2>> srt;
auto a = Q;
for ( int i = 0; i < n; i++ ){
srt.pb({Q[i], -1});
}
for ( int i = 0; i < m; i++ ){
srt.pb({S[i], i});
a.pb(S[i]);
}
sort(all(a));
sort(all(srt));
vector <int> p(m);
for ( int i = 0; i < n + m; i++ ){
auto [val, j] = srt[i];
if ( j != -1 ) p[j] = i;
}
vector <vector<int>> er_(d * 2);
int opt = 1e9, mx = *max_element(all(P)), _ip = 0;
for ( int l = 0; l < d; l++ ){
while ( _ip < n && P[_ip] < l ){
chmax(mx, P[_ip] + d);
_ip++;
}
auto ok = [&](int x){ return x >= 0 && x < n + m; };
int maxDiff = 0;
multiset <int> st;
vector <int> L_(n + m), R_(n + m);
for ( int i = 0; i < n + m; i++ ){
L_[i] = i - 1; R_[i] = i + 1;
if ( ok(L_[i]) ){
chmax(maxDiff, a[i] - a[L_[i]]);
}
if ( ok(R_[i]) ){
chmax(maxDiff, a[R_[i]] - a[i]);
}
st.insert(a[i]);
}
for ( int i = 0; i < m; i++ ){
int v = (R[i] < l ? R[i] + d : R[i]);
er_[v].pb(i);
}
auto er = [&](int j){
j = p[j];
st.erase(st.find(a[j]));
if ( ok(R_[j]) ){
L_[R_[j]] = L_[j];
}
if ( ok(L_[j]) ){
R_[L_[j]] = R_[j];
}
if ( ok(L_[j]) && ok(R_[j]) ){
chmax(maxDiff, a[R_[j]] - a[L_[j]]);
}
};
for ( int r = l; r <= l + d; r++ ){
for ( auto &j: er_[r] ){
er(j);
} er_[r].clear();
if ( r >= mx ){
auto tmp = chmin(opt, (r - l + 1) * (min(*st.rbegin() - *st.begin() + 1, d - maxDiff + 1)));
/*if ( tmp > 0 ){
cout << l << " " << r << " -> " << opt << " cur len : " << *st.rbegin() - *st.begin() + 1 << " maxDiff : " << maxDiff << ln;
for ( auto &u: st ) cout << u << ' '; cout << ln;
}*/
}
}
}
cout << opt;
cout << '\n';
}
/*
Wrong Answer on Test :
2 2 5
4 0
1 1
0 0
2 2
Expected
8
Your out :
4
*/
