题目描述

为普及8G网络，Kiana决定在全国各地建立起8G基站来，此计划的第一步就是在某些已经侦测好的位置中选出几个地点来，建设测试基站以供实验。

Kiana的团队一共侦测了\(n\)个地点，其中第\(i\)个地点的可靠度为\(R_i\)，有\(m\)条光纤架在这些地点之间，每条光纤都将两个地点连接了起来，且光纤是双向的。测试基站是由\(4\)座信号塔一组构成的，信号塔只能建立在侦测好的地点上，且每个地点最多建立\(1\)座信号塔。

在这\(4\)座信号塔中，有\(2\)座信号塔为主信号塔，另外\(2\)座为副信号塔，为保证实验顺利进行，Kiana规定每组测试基站中的每座主信号塔必须与其它\(3\)座信号塔通过光纤直接相连，而每座副信号塔必须与该组基站中的主信号塔直接相连，但副信号塔之间不必有光纤连接（如果有的话，也不违反规定）。

经过计算，Kiana发现假设选择第\(i,j\)个地点建立主信号塔，第\(p,q\)个地点建立副信号塔，测试基站的总可靠度为主信号塔所在地可靠度加1后的乘积加上副信号塔所在地可靠度的乘积，即总可靠度\(S=(R_i+1)\times (R_j+1)+R_p\times R_q\)。

现在Kiana团队想建设一组测试基站，她想知道选取哪几个地点建立信号塔能使得测试基站的总可靠度最大。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数\(n\)和\(m\)，分别表示Kiana团队侦测好的地点数量与这些地点之间架有的光纤数量。

第二行包含\(n\)个正整数，其中第\(i\)个数\(R_i\)表示第\(i\)个地点的可靠度。

接下来\(m\)行，每行包含两个正整数\(u\)和\(v\)，表示在第\(u\)个地点和第\(v\)个地点之间架有光纤，数据保证\(u\neq v\)，且两个地点之间至多架有一条光纤。数据还保证至少存在一种合法的基站建设方式，即Kiana团队总可以选出\(4\)个符合条件的地点建立信号塔。

输出格式

输出共一行，包含一个正整数，表示Kiana能建设起的基站的最大总可靠度。

输入输出样例

输入样例#1：

4 6
3 5 7 9 
1 2
1 3
1 4
2 3
2 4
3 4

输出样例#1：

95

输入样例#2：

station2.in

输出样例#2：

station2.ans

样例解释

Kiana团队共测绘了\(4\)个地点，其可靠度依次为\(3,5,7,9\)，这些地点之间一共架有\(6\)条光纤，其中任意两个地点之间都有光纤连接。Kiana团队有\(6\)种合法的基站建设方案：

• 选择第\(1,2\)个地点建立主信号塔，第\(3,4\)个地点建立副信号塔，这种方案的总可靠度为\((3+1)\times (5+1)+7\times 9=87\)

• 选择第\(1,3\)个地点建立主信号塔，第\(2,4\)个地点建立副信号塔，这种方案的总可靠度为\((3+1)\times (7+1)+5\times 9=77\)

• 选择第\(1,4\)个地点建立主信号塔，第\(2,3\)个地点建立副信号塔，这种方案的总可靠度为\((3+1)\times (9+1)+5\times 7=75\)

• 选择第\(2,3\)个地点建立主信号塔，第\(1,4\)个地点建立副信号塔，这种方案的总可靠度为\((5+1)\times (7+1)+3\times 9=75\)

• 选择第\(2,4\)个地点建立主信号塔，第\(1,3\)个地点建立副信号塔，这种方案的总可靠度为\((5+1)\times (9+1)+3\times 7=81\)

• 选择第\(3,4\)个地点建立主信号塔，第\(1,2\)个地点建立副信号塔，这种方案的总可靠度为\((7+1)\times (9+1)+3\times 5=95\)

所以Kiana团队选择最后一种建设方案，此时总可靠度最大为\(95\)。

数据范围

对于\(10\%\)的数据，保证\(1\leq n\leq 50,1\leq m\leq 25\)。

对于\(20\%\)的数据，保证\(1\leq n\leq 50,1\leq m\leq 200\)。

对于\(30\%\)的数据，保证\(1\leq n\leq 500,1\leq m\leq 250\)。

对于\(40\%\)的数据，保证\(1\leq n\leq 500,1\leq m\leq 2000\)。

对于\(60\%\)的数据，保证\(1\leq n\leq 50000,1\leq m\leq 25000\)。

对于\(100\%\)的数据，保证\(1\leq n\leq 50000,1\leq m\leq 2\times 10^5,1\leq R_i\leq 10^4\)。

有六组数据满足每一个被光纤连接起来构成的连通块内，任意两个地点之间都有光纤连接。