给你一个长度为 $$$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$$$ 都出现在数组 $$$a$$$ 中。保证存在这样的一对。
输入
第一行包含一个整数 $$$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 < y_i \le 10^9$$$),它们代表一个坏对。确保输入中不会出现两次坏对。还保证 $$$cnt_{x_i} > 0$$$ 且 $$$cnt_{y_i} > 0$$$。
保证每个测试用例都有一对整数 $$$(u, v)$$$, $$$u \ne v$$$,这还不错,并且这两个数字都出现在 $$$a$$$ 中。
保证$$$n$$$的总和与$$$m$$$的总和不超过$$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
3 6 1 6 3 6 7 3 3 3 6 2 0 3 4 7 4 1 2 2 3 1 5 1 1 5 3 5 1 3 2 5
输出 #1
40 14 15
注意
在第一个测试用例中,$$$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$$$。