主菜を一つずつ試します。副菜については、事前に価格の降順にソートしておき、いま調べている主菜と組み合わせられるものを発見したら終了することにします。すると合計で高々 \(N + L\) 品の副菜を試すことになり、\(O(M \log M + N + L)\) 時間の解法を得ます（ある主菜と副菜が組み合わせられるかの判定は、ハッシュ集合を使えば定数時間で行えます）。

実装例（Python）

N, M, L = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
g = [set() for _ in range(N)]
for _ in range(L):
    c, d = map(lambda x: int(x) - 1, input().split())
    g[c].add(d)

s = sorted([(p, j) for j, p in enumerate(b)], reverse=True)
ans = 0
for i in range(N):
    for p, j in s:
        if j not in g[i]:
            ans = max(ans, a[i] + p)
            break
print(ans)