34686번 - Rescue Squad 다국어

문제

As a town leader, you must form a rescue squad to help a neighboring town under attack by monsters. There are $n$ knights in your town, numbered from 1ドル$ to $n,ドル and a knight $i$ (1ドル ≤ i ≤ n$) has a positive integer level $L_i$. For efficient monster hunting, the knights who form the rescue squad must be able to trust one another. The trust relationship $T$ between two knights $i$ and $j$ (1ドル ≤ i < j ≤ n$) is defined as follows:

$T(i,j) = 1,ドル if $i$ and $j$ trust each other;

$T(i,j) = 0,ドル if they do not.

The rescue squad $S$ is a set of four distinct knights, and each knight in the squad must have a trust relationship $T = 1$ with at least two of the other three. The ability of $S,ドル Ability($S$), is defined as the sum of the levels of the four knights in $S$.

For example, suppose that $n = 5$ and the levels of the five knights are $L_1 = 3,ドル $L_2 = 2,ドル $L_3 = 3,ドル $L_4 = 7,ドル and $L_5 = 1$. If the trust relationship is defined as $T(1, 2) = T(2, 3) = T(3, 4) = T(1, 3) = T(1, 4) = T(1, 5) = 1$ and $T(2, 4) = T(2, 5) = T(3, 5) = T(4, 5) = 0,ドル then $S = \{1, 2, 3, 4\}$ is the only possible rescue squad, and Ability($S$) is 15ドル$.

Given the levels of $n$ knights and their trust relationships, write a program to find a squad $S$ for which Ability($S$) is maximized and output its ability value.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $m$ (4ドル ≤ n ≤ 1,000円$; 1ドル ≤ m ≤ \min (\frac{n(n-1)}{2}, 25,000円)$), where $n$ is the number of knights and $m$ is the number of pairs of knights $(i,j)$ such that $T(i,j) = 1$ and $i < j$. In the following $n$ lines, the $i$-th line contains a positive integer that represents the level $L_i$ (1ドル ≤ L_i ≤ 10,000円$) of the knight $i$. In the following $m$ lines, each line contains two integers, $i$ and $j$ (1ドル ≤ i < j ≤ n$) that represent a trust relationship $T(i,j) = 1$. There are no duplicate entries among the $m$ lines describing the trust relationships, and for any pair of knights $i'$ and $j'$ that do not appear in the input, $T(i',j') = 0$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the ability Ability($S$) of a squad $S$ with the maximum ability among the squads that can be formed. If no squad can be formed, print $-1$.

제한

노트