E. Лучшая пара
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ размера $$$n$$$. Пусть $$$cnt_x$$$ — количество элементов исходного массива, равных $$$x$$$. Определим $$$f(x, y)$$$ как $$$(cnt_x + cnt_y) \cdot (x + y)$$$.

Также даны $$$m$$$ плохих пар $$$(x_i, y_i)$$$. Обратите внимание, что если $$$(x, y)$$$ плохая пара, то $$$(y, x)$$$ тоже плохая.

Найдите максимальное значение $$$f(u, v)$$$ по всем парам $$$(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$$$) — элементы массива.

$$$i$$$-я из следующих $$$m$$$ строк содержат два целых числа $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — ответ на задачу.

Пример
Входные данные
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
Выходные данные
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$$$.