\(A,B\) が降順にソートされているとします。

まず、第一目標が達成可能となる必要十分条件は \(i=1,2,\ldots,M\) に対し \(A_i \geq B_i\) が成り立つことです。

証明：

十分性：依頼 \(i\) に対して配達員 \(i\) を割り当てると \(A_i \geq B_i\) より全依頼を処理できます。

必要性：ある \(i\) に対して \(A_i < B_i\) とすると、要求値が \(B_i\) 以上の依頼が少なくとも \(i\) 件あります。これら \(i\) 件はどれも体力が \(B_i\) 以上の配達員が必要ですが、\(A_i < B_i\) より体力が \(B_i\) 以上の配達員は \(i\) 人未満しかいません。したがって、最初の仮定の元では第一目標は達成不可能となります。

次に、第一目標が達成可能という条件のもとで \(A_i = B_j\) となるペアの最大化を考えます。

\(C_A(x)\) を \(A\) に \(x\) が登場する回数とします。\(C_B(x)\) も同様に定義します。

このとき、求める値は \(\displaystyle \sum_x \min(C_A(x),C_B(x))\) と一致します。

証明：

\(X=\displaystyle \sum_x \min(C_A(x),C_B(x))\) とします。明らかに答えは \(\displaystyle X\) 以下です。

第一目標を満たすが ぴったりの割り当て の個数が \(X\) 未満である割り当てを \(1\) つ取ります。このとき、ある \(x\) が存在して値が \(x\) であるような ぴったりの割り当て が \(\min(C_A(x),C_B(x))\) 個未満となります。つまり、

• 体力が \(x\) で、要求 \(x\) の依頼に割り当てられていない配達員
• 要求が \(x\) で、体力 \(x\) の配達員に割り当てられていない配達依頼

の両方が存在します。

前者の状況を満たす配達員はどの依頼にも割り当てられていないか要求が \(x\) 未満であるような依頼に割り当てられています。どの依頼にも割り当てられていない場合はそのまま配達員を変更すれば良いです。要求が \(x\) 未満であるような依頼に割り当てられている場合、その配達員と要求 \(x\) に割り当てられた配達員を swap することで第一目標を達成しつつ ぴったりの割り当て の個数を \(1\) 増やすことができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N \log N)\) です。

実装例(Python3)

from collections import Counter

n, m = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
if any(a[i] < b[i] for i in range(m)):
    print(-1)
else:
    ca = Counter(a)
    cb = Counter(b)
    print(sum(min(ca[x], cb[x]) for x in cb))