この問題はいくつかの解法が考えられますが、本解説では優先度付きキューを利用した解法を説明します。

はじめに、大まかな方針として次のようなアルゴリズムを考えます。

• 提供されている定食を発見するまで次の操作を繰り返す。
  • まだ選んでいない主菜と副菜の組のうち、価格の和が最も高い組のうち 1 つを(何か高速な方法で)選ぶ。
  • その組が提供されている定食である場合は、その定食の価格を答えとして出力して操作を全て終了する。

このアルゴリズムのループは高々 \(L + 1\) 回しか回りません。よって、上のアルゴリズム内の「(何か高速な方法で)」という部分で適切なアルゴリズムを構成できればこの問題を十分高速に解くことが出来ます。

選んでいない主菜と副菜のうち価格の和が最も高い組を高速に発見する方法を説明します。
説明の簡単のため \(b_1 \geq b_2 \geq \dots \geq b_M\) とします。(そうでない場合は \(b\) を降順にソートしたときの index を利用すればよいです。) このとき、以下の手順によって価格の和が最も高い組を取り出す操作を実行することができます。

• 補助変数として長さ \(M\) の配列 cur を用意する。cur[i] は「主菜が \(i\) の定食をどこまで調べたか」を意味する配列で、はじめ cur[i] = 1 で初期化されている。
• (コスト, 主菜の種類) の組を格納してコスト降順に取り出す優先度付きキュー Q を用意する。
• \(i=1, 2, \dots, N\) について、Q に \((a_i + b_1, i)\) を追加する。
• 選んでいない主菜と副菜のうち価格の和が最も高い組を取り出す操作は次のように行う。
  • \(Q\) の先頭の要素を \((c, i)\) とする。\(Q\) の先頭の要素を pop する。価格の和が最も高い主菜と副菜の組は \((i, \mathrm{cur}[i])\) である。
  • その後、cur[i] に\(1\) を加算する。
  • cur[i] が \(M\) 以下である場合は Q に \((a_i + b_\mathrm{cur[i]}, i)\) を追加する。

正当性については、「調べていない組のうちコスト最大である組が Q に必ず格納されている」という事実を証明することで確認できます。選挙のドント方式を知っている人は、ドント方式に似たアルゴリズムとして捉えると分かりやすいかもしれません。

以上のアルゴリズムを適切に実装することで、この問題を \(\mathrm{O}(L (\log N + \log L) + N + M \log M)\) で解くことが出来て、これは十分高速です。

#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);
  }
}