AT_joi2025_yo2_d 親密なシェフ (Intimate Chef)

在一家玻利维亚菜餐厅，有 $N$ 名厨师，每位厨师编号为 $1$ 到 $N$。第 $i$ 位厨师（$1 \leq i \leq N$）可以制作美味度为 $A_i$ 的 Silpancho 和美味度为 $B_i$ 的 Pique Macho。 然而，由于厨师们性格各异，有 $M$ 对厨师关系不佳。第 $j$ 对关系不佳的厨师组合（$1 \leq j \leq M$）为厨师 $U_j$ 和厨师 $V_j$。 顾客在这家餐厅点餐的具体规则如下： - 顾客会选择满足 $1 \leq p < q \leq N$ 的整数 $p, q$，要求厨师 $p$ 和厨师 $q$ 这两人出菜。不能选择关系不佳的厨师组合。 - 对于两道菜 Silpancho 和 Pique Macho，每道菜都由这两位厨师中美味度更高的一位来制作。如果两人的美味度相同，则其中任意一人可以制作。需要注意，同一位厨师可以制作两道菜。 - 顾客的**满意度**为两道菜的美味度之和。 现有 $Q$ 位编号为 $1$ 到 $Q$ 的顾客来到餐厅。 第 $k$ 位顾客（$1 \leq k \leq Q$）会在可以选择的所有两人组合中，选择第 $X_k$ 高的满意度的厨师两人组进行点餐。具体来说，设满意度为 $S$，则根据 $S \times N^2 + p \times N + q$ 从大到小排序，第 $X_k$ 个为选择的 ($p$, $q$)。 给定所有厨师和顾客的信息，请编写程序计算第 $k$ 位顾客（$1 \leq k \leq Q$）的满意度。

输入格式如下： > $N\ M\ Q$ > $A_1\ A_2\ \cdots\ A_N$ > $B_1\ B_2\ \cdots\ B_N$ > $U_1\ V_1$ > $U_2\ V_2$ > $\vdots$ > $U_M\ V_M$ > $X_1\ X_2\ \cdots\ X_Q$

输出 $Q$ 行，每行输出一个整数，第 $k$ 行输出第 $k$ 位顾客的满意度。

## 小数据范围 1.（$4$ 分）$N \leq 50$，$M \leq 50$，$Q \leq 50$，$X_k \leq 50$（$1 \leq k \leq Q$）。 2.（$9$ 分）$B_i = 1$（$1 \leq i \leq N$），$M = 0$，$Q = 1$。 3.（$10$ 分）$B_i = 1$（$1 \leq i \leq N$），$Q = 1$。 4.（$5$ 分）$B_i = 1$（$1 \leq i \leq N$）。 5.（$29$ 分）$N \leq 100\,000$，$M \leq 100\,000$，$Q = 1$，$X_1 = 1$。 6.（$14$ 分）$N \leq 100\,000$，$M \leq 100\,000$，$Q = 1$，$X_1 \leq 100\,000$。 7.（$18$ 分）$N \leq 100\,000$，$M \leq 100\,000$，$Q \leq 100\,000$，$X_k \leq 100\,000$（$1 \leq k \leq Q$）。 8.（$11$ 分）无其他附加约束。 ## 样例解释 1 可以选择出菜的厨师两人组有 $4$ 组，对应顾客的满意度如下： - 选择厨师 $1$ 和厨师 $2$ 时，Silpancho 由厨师 $2$ 制作，Pique Macho 由厨师 $1$ 制作。因此 Silpancho 的美味度为 $7$，Pique Macho 的美味度为 $4$，顾客满意度为 $7 + 4 = 11$。 - 选择厨师 $1$ 和厨师 $4$ 时，两道菜均由厨师 $4$ 制作。因此美味度分别为 $5$ 和 $8$，满意度为 $5 + 8 = 13$。 - 选择厨师 $2$ 和厨师 $3$ 时，Silpancho 由厨师 $2$ 制作，Pique Macho 由厨师 $3$ 制作，满意度为 $7 + 4 = 11$。 - 选择厨师 $3$ 和厨师 $4$ 时，两道菜均由厨师 $4$ 制作，美味度分别为 $5$ 和 $8$，满意度为 $5 + 8 = 13$。 因此，各顾客的情况如下： - 顾客 $1$ 选择的是厨师 $3$ 和厨师 $4$，满意度是 $13$。 - 顾客 $2$ 选择的是厨师 $1$ 和厨师 $4$，满意度是 $13$。 - 顾客 $3$ 选择的是厨师 $2$ 和厨师 $3$，满意度是 $11$。 - 顾客 $4$ 选择的是厨师 $1$ 和厨师 $2$，满意度是 $11$。 此输入例满足小数据范围 $1,7,8$ 的约束。 ## 样例解释 2 可以选择的厨师两人组合有 $3$ 组，对应顾客满意度如下： - 选择厨师 $1$ 和厨师 $3$ 时，Silpancho 由厨师 $3$，Pique Macho 可由$1$或$3$制作，美味度分别为 $5$ 和 $1$，合计满意度为 $6$。 - 选择厨师 $1$ 和厨师 $4$ 时，Silpancho 由厨师 $4$，Pique Macho 可由$1$或$4$制作，美味度为 $4$ 和 $1$，合计满意度为 $5$。 - 选择厨师 $3$ 和厨师 $4$ 时，Silpancho 由厨师 $3$，Pique Macho 可由$3$或$4$制作，美味度均为 $5$ 和 $1$，合计满意度为 $6$。 因此，顾客 $1$ 选择的是厨师 $3$ 和厨师 $4$，满意度为 $6$。 此输入例满足小数据范围 $1,3,4,5,6,7,8$ 的约束。 ## 样例解释 3 此输入例满足小数据范围 $1,7,8$ 的约束。 ## 样例解释 4 此输入例满足小数据范围 $1,7,8$ 的约束。 ## 数据范围与限制 - $2 \leq N \leq 400\,000$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq B_i \leq 10^9$（$1 \leq i \leq N$）。 - $0 \leq M \leq 400\,000$。 - $M < \frac{N(N - 1)}{2}$。 - $1 \leq U_j < V_j \leq N$（$1 \leq j \leq M$）。 - $(U_i, V_i) \neq (U_j, V_j)$（$1 \leq i < j \leq M$）。 - $1 \leq Q \leq 400\,000$。 - $1 \leq X_k \leq 400\,000$（$1 \leq k \leq Q$）。 - $X_k \leq \frac{N(N - 1)}{2} - M$。 - 所有输入的数均为整数。 由 ChatGPT 5 翻译