- #pragma GCC optimize("Ofast,unroll-loops")
- #pragma GCC target("avx,avx2,sse,sse2,sse3,fma")
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define fi first
- #define se second
- #define pb emplace_back
- #define all(n) (n).begin(),(n).end()
- #define mem(n,x) memset(n,x,sizeof(n))
- #define IOS ios::sync_with_stdio(0),cin.tie(0)
- #define pii pair<ll,ll>
- #define vi vector<ll>
- #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
- #define int ll
- template<typename A> void _do(A x){ cerr<<x<<"\n"; }
- template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
- ll n,m;
- ll area(pii x, pii y){
- if(x.fi > y.fi || x.se > y.se) return -100;
- return (y.fi - x.fi) * (y.se - x.se);
- }
- signed main(){
- IOS;
- cin>>n>>m;
- deque<pii> sell(n), buy(m);
- for(int i=0;i<n;i++){
- cin>>sell[i].fi>>sell[i].se;
- }
- for(int i=0;i<m;i++){
- cin>>buy[i].fi>>buy[i].se;
- }
- sort(all(sell));
- sort(all(buy));
- deque<pii> tmp;
- for(auto i:sell){
- if(tmp.size() && i.se > tmp.back().se) continue;
- tmp.pb(i);
- }
- sell = tmp;
- tmp.clear();
- for(auto i:buy){
- while(tmp.size() && i.se > tmp.back().se) tmp.pop_back();
- tmp.pb(i);
- }
- buy = tmp;
- deque<pii> dq;
- while(!sell.empty() && !buy.empty() && area(sell[0],buy[0]) <= 0){
- if(sell[0].fi >= buy[0].fi) buy.pop_front();
- else if(sell[0].se >= buy[0].se) sell.pop_front();
- else assert(false);
- }
- /* for(auto i:sell) cout<<i.fi<<" "<<i.se<<" "; cout<<'\n'; */
- /* for(auto i:buy) cout<<i.fi<<" "<<i.se<<" "; cout<<'\n'; */
- for(int i=0,siz=sell.size();i<siz;i++){
- while(dq.size()){
- auto &[pid,pl] = dq.back();
- if(area(sell[i],buy[pl]) <= area(sell[pid],buy[pl])) break;
- dq.pop_back();
- }
- if(dq.empty()){
- dq.pb(i,0);
- }
- else{
- int l = dq.back().se, r = buy.size(), pid = dq.back().fi;
- while(l<r){
- int m = (l+r)/2;
- ll cura = area(sell[i], buy[m]), prea = area(sell[pid], buy[m]);
- /* dbg(m, cura, prea); */
- if(cura < 0 && prea < 0){
- if(buy[m].fi < sell[i].fi) l = m + 1;
- else r = m;
- }
- else if(cura < 0 || prea >= cura) l = m + 1;
- else r = m;
- }
- if(l < buy.size() && area(sell[i], buy[l]) > 0) dq.pb(i,l);
- }
- }
- /* for(auto i:dq) cout<<i.fi<<" "<<i.se<<'\n'; */
- if(dq.empty()) return cout<<0<<'\n', 0;
- ll ans = 0;
- for(int i=0;i<buy.size();i++){
- while(dq.size() >= 2 && dq[1].se <= i) dq.pop_front();
- /* dbg(dq[0].fi, i); */
- ans = max(ans, area(sell[dq[0].fi], buy[i]));
- }
- cout<<ans<<'\n';
- }