#P1637E. Best Pair

    ID: 136 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forceimplementation*2100

Best Pair

Description

You are given an array aa of length nn. Let cntxcnt_x be the number of elements from the array which are equal to xx. Let's also define f(x,y)f(x, y) as (cntx+cnty)(x+y)(cnt_x + cnt_y) \cdot (x + y).

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

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

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

The first line of each test case contains two integers nn and mm (2n31052 \le n \le 3 \cdot 10^5, 0m31050 \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 nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9) — elements of the array.

The ii-th of the next mm lines contains two integers xix_i and yiy_i (1xi<yi1091 \le x_i < 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 cntxi>0cnt_{x_i} > 0 and cntyi>0cnt_{y_i} > 0.

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

It is guaranteed that the total sum of nn and the total sum of mm don't exceed 31053 \cdot 10^5.

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

Input

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

The first line of each test case contains two integers nn and mm (2n31052 \le n \le 3 \cdot 10^5, 0m31050 \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 nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9) — elements of the array.

The ii-th of the next mm lines contains two integers xix_i and yiy_i (1xi<yi1091 \le x_i < 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 cntxi>0cnt_{x_i} > 0 and cntyi>0cnt_{y_i} > 0.

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

It is guaranteed that the total sum of nn and the total sum of mm don't exceed 31053 \cdot 10^5.

Output

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

Samples

样例输入 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

Note

In the first test case 33, 66, 77 occur in the array.

  • f(3,6)=(cnt3+cnt6)(3+6)=(3+2)(3+6)=45f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45. But (3,6)(3, 6) is bad so we ignore it.
  • f(3,7)=(cnt3+cnt7)(3+7)=(3+1)(3+7)=40f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40.
  • f(6,7)=(cnt6+cnt7)(6+7)=(2+1)(6+7)=39f(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\max(40, 39) = 40.