Дан массив \(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\). Гарантируется, что хотя бы одна такая пара существует.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В первом тестовом случае в массиве встречаются значения \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
40
14
15
|