CF1637E.Best Pair

You are given an array $a$ of length $n$. Let $cnt_x$ be the number of elements from the array which are equal to $x$. Let's also define $f(x, y)$ as $(cnt_x + cnt_y) \cdot (x + y)$.

Also you are given $m$ bad pairs $(x_i, y_i)$. Note that if $(x, y)$ is a bad pair, then $(y, x)$ is also bad.

Your task is to find the maximum value of $f(u, v)$ over all pairs $(u, v)$, such that $u \neq v$, that this pair is not bad, and also that $u$ and $v$ each occur in the array $a$. It is guaranteed that such a pair exists.

给你一个长度为 $n$ 的数组 $a$。令 $cnt_x$ 表示数组中等于 $x$ 的元素个数。再定义函数 $f(x, y) = (cnt_x + cnt_y) \cdot (x + y)$。

此外，你还会得到 $m$ 个“坏”数对 $(x_i, y_i)$。注意：若 $(x, y)$ 是坏数对，则 $(y, x)$ 也是坏数对。

你的任务是：在所有满足以下条件的数对 $(u, v)$ 中，找出 $f(u, v)$ 的最大值：

• $u \neq v$；
• $(u, v)$ 不是坏数对；
• $u$ 和 $v$ 均在数组 $a$ 中出现过。

题目保证至少存在一个满足条件的数对。

The first line contains a single integer $t$ ($1 \le t \le 10\,000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$, $0 \le m \le 3 \cdot 10^5$) — the length of the array and the number of bad pairs.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.

The $i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \lt y_i \le 10^9$), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that $cnt_{x_i} \gt 0$ and $cnt_{y_i} \gt 0$.

It is guaranteed that for each test case there is a pair of integers $(u, v)$, $u \ne v$, that is not bad, and such that both of these numbers occur in $a$.

It is guaranteed that the total sum of $n$ and the total sum of $m$ don't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10\,000$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$0 \le m \le 3 \cdot 10^5$）—— 数组的长度和坏对的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 数组的元素。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \lt y_i \le 10^9$），表示一个坏对。保证输入中不会重复出现同一个坏对。同时保证 $cnt_{x_i} \gt 0$ 且 $cnt_{y_i} \gt 0$。

保证对于每个测试用例，均存在一对整数 $(u, v)$（其中 $u \ne v$），该对不是坏对，且 $u$ 和 $v$ 均在数组 $a$ 中出现。

保证所有测试用例的 $n$ 之和以及所有测试用例的 $m$ 之和均不超过 $3 \cdot 10^5$。

For each test case print a single integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first test case $3$, $6$, $7$ occur in the array.

• $f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45$. But $(3, 6)$ is bad so we ignore it.
• $f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40$.
• $f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39$.

The answer to the problem is $\max(40, 39) = 40$.

在第一个测试用例中，数组中出现的数为 $3$、$6$、$7$。

• $f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45$。但 $(3, 6)$ 是坏对，因此忽略它。
• $f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40$。
• $f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39$。

该问题的答案为 $\max(40, 39) = 40$。