There are several approaches to this problem. In this editorial, we explain one that uses a priority queue.

First of all, we outline the algorithm as follows:

• Repeat the following operations until an available meal is found.
  • Find (somehow) a pair of main dish and side dish with the highest price among those not enumerated yet.
  • If a set meal with that pair is actually offered, print its price and terminate the entire procedure.

The repetition is performed at most \((L+1)\) times. Thus, once we construct a proper algorithm for the “somehow” above, the problem can be solved fast enough.

We describe how to find an unseen pair of main dish and side dish with the highest price fast.
For simplicity, we assume that \(b_1 \geq b_2 \geq \dots \geq b_M\) (otherwise, we can use the indices when \(b\) is sorted in descending order). Then, one can obtain a pair with the highest price by the following procedure.

• Let cur be an auxiliary variable, which is an array of length \(N\). cur[i] maintains the index of side meal paired with main dish \(i\), initialized with cur[i] = 1.
• Prepare a priority queue Q that stores (cost, index of main dish) and supports retrieval of one with the maximum cost.
• For each \(i=1, 2, \dots, N\), insert \((a_i + b_1, i)\) to \(i\).
• One can find a pair of main dish and side dish with the highest price among those not enumerated yet as follows:
  • Let \((c,i)\) be the topmost element in \(Q\). Pop the topmost element from \(Q\). The sought pair with the highest price is \((i, \mathrm{cur}[i])\).
  • Then, add \(1\) to cur[i].
  • If cur[i] is no greater than \(M\), insert \((a_i + b_\mathrm{cur[i]}, i)\) into Q.

This algorithm is justified by proving the fact that Q always store an unseen pair with the maximum cost. If you know D’Hondt method in electoral system, it may be easier to consider it as a D’Hondt-method-like one.

By appropriately implement the algorithm above, the problem can be solved in a total of \(\mathrm{O}(L (\log N + \log L) + N + M \log M)\) time, which is fast enough.

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;
int main() {
  int N, M, L;
  cin >> N >> M >> L;
  vector<int> a(N), b(M);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  set<pair<int, int>> bad;
  for (int i = 0; i < L; i++) {
    int c, d;
    cin >> c >> d;
    bad.emplace(c - 1, d - 1);
  }

  vector<int> ord_b(M);
  for (int i = 0; i < M; i++) ord_b[i] = i;
  sort(begin(ord_b), end(ord_b), [&](int i, int j) { return b[i] > b[j]; });

  vector<int> cur(N);
  priority_queue<pair<int, int>> Q;
  for (int i = 0; i < N; i++) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  while (true) {
    auto [cost, i] = Q.top();
    int j = cur[i];
    Q.pop();
    if (bad.count({i, ord_b[j]}) == 0) {
      cout << cost << "\n";
      break;
    }
    cur[i]++;
    if (cur[i] != M) Q.emplace(a[i] + b[ord_b[cur[i]]], i);
  }
}