ピースの個数 \((A+1)(B+1)\) は非常に大きくなりうる（最大 \(4 \times 10^{10}\) 程度）ので、すべてのピースを愚直に扱う方法では計算量が過大になり、本問題に正解することは困難です。 一方で、実際にイチゴが \(1\) 個以上載るピースの個数は \(N\) （最大 \(2 \times 10^5\) ）以下と、比較的少ないです。 そこで、イチゴが \(1\) 個以上載っているピースの情報だけを取り扱うことで計算量を削減する方針を取ります。

本問題の答えである、高橋君が食べるイチゴの個数の最小値 \(m\) と最大値 \(M\) を求めるには、

1. イチゴが \(1\) 個以上の載っているピースの個数
2. イチゴが \(1\) 個以上の載っているピースそれぞれの、載っているイチゴの個数

の \(2\) つの情報があれば十分です。

実際、\(M\) を求めるには、上記 2. の情報を用いてイチゴが \(1\) 個以上載っているピースそれぞれのイチゴの個数を調べ、その中の最大値を取れば良いです。

また、\(m\) については、

• まずイチゴが \(1\) 個以上載っているピースの個数（上記 1. の情報）がピースの総数 \((A+1)(B+1)\) より少ない場合は、イチゴが \(1\) 個も載っていないピースが \(1\) つはあることになるため、\(m = 0\) です。
• そうでない場合は、上記 2. の情報を用いて \(1\) 個 以上載っているピースそれぞれのイチゴの個数を調べれば、その中の最小値として求まります。

そこで、上記の情報 1. と情報 2. を求める方法を以下で考えます。

\(x\) 軸の正の方向を右、\(y\) 軸の正の方向を上とし、便宜上 \(a_{A+1} \coloneqq W, b_{B+1} \coloneqq H\) と定めます。 また、全 \((A+1)(B+1)\) 個あるピースは、横 \(A+1\) 列、縦 \(B+1\) 行のグリッド状に並んでいますが、各 \(X = 1, 2, \ldots, A+1\) と各 \(Y = 1 ,2, \ldots, B+1\) について、左から \(X\) 列目、下から \(Y\) 行目にあるピースの ID を \((X, Y)\) と定めます。

このとき、座標 \((p, q)\) にあるイチゴが載っているピースの ID は、 \(p \leq a_X\) を満たす最小の \(X\) と、\(q \leq b_Y\) を満たす最小の \(Y\) によって、\((X, Y)\) と表されます。 この「 \(p \leq a_X\) を満たす最小の \(X\) 」と、「 \(q \leq b_Y\) を満たす最小の \(Y\) 」はそれぞれ単調増加な数列 \((a_1, a_2, \ldots, a_{A+1})\) と \((b_1, b_2, \ldots, b_{B+1})\) 上で二分探索することで求められるので、 与えられたイチゴの座標 \((p, q)\) に対して、そのイチゴが載っているピースの ID は \(O(\log A + \log B)\) 時間で求められます。

よって、\(N\) 個のイチゴそれぞれについて、それが載っているピースの ID \((X_i, Y_i)\)を 並べた列

\[(X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N)\]

は、\(O(N(\log A + \log B))\) 時間で得られます。 求めたい情報 1. はこの列に何種類の ID が現れるか、情報 2. はこの列に \(1\) 回以上現れる ID にそれぞれについての出現回数に対応しますが、これは連想配列を用いることで求めることができます。

以上より、連想配列へのアクセスが、そのエントリ数 \(z\) に対して \(1\) 回あたり \(O(\log z)\) 時間で実現できるとき、 本問題を \(O(N(\log A + \log B + \log N) + A + B)\) 時間で解くことができます。

以下に、本問題の C++ 言語による正解例を記載します。

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

ll w, h;
ll n, A, B;
ll p[200001], q[200001];
ll a[200002], b[200002];

int main(void)
{
  cin >> w >> h;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> p[i] >> q[i];
  cin >> A;
  for(int i = 1; i <= A; i++) cin >> a[i];
  cin >> B;
  for(int i = 1; i <= B; i++) cin >> b[i];
  a[A+1] = w, b[B+1] = h;
  
  map<pair<ll, ll>, ll> mp;
  for(int i = 1; i <= n; i++){
    ll X = *lower_bound(a+1, a+A+2, p[i]);
    ll Y = *lower_bound(b+1, b+B+2, q[i]);
    mp[{X, Y}]++;
  }
  
  ll m = n, M = 0;
  for(auto p : mp) M = max(M, p.second);
  if(mp.size() == (A+1)*(B+1)){
    for(auto p : mp) m = min(m, p.second);
  }
  else m = 0;
  cout << m << " " << M << endl;
  
  return 0;
}