We will try the main dishes one by one. As for the side dishes, we will sort them in descending order of price in advance, and we will finish as soon as we find one that can be combined with the main dish we are currently investigating. As a result, we will end up trying at most \(N + L\) side dishes in total, and we obtain a solution that takes \(O(M \log M + N + L)\) time (you can check whether a certain main dish and side dish can be combined in constant time using a hash set).

Sample Implementation (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)