F. Photography
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Paulliant loves photography. Today, he arrived in Harbin to take photos at various landmarks. For simplicity, Harbin can be represented as a undirected graph with $$$n$$$ nodes and $$$m$$$ edges, where each node represents a different landmark and each edge represents a road connecting these landmarks. Paulliant will choose a landmark to start his photography tour. Once he finishes taking photos at one landmark, he will travel along the edges to his next preferred landmark to continue his tour. Due to time constraints, he can visit at most $$$5$$$ distinct landmarks. Naturally, Paulliant does not want to repeat his visits, so these landmarks must be different. Before the tour, Paulliant has assigned a "happiness value" to each landmark, where the $$$i$$$-th landmark has a happiness value $$$a_i$$$. Paulliant wants the total happiness value from all the landmarks he visits to be maximized. Determine the maximum total happiness value Paulliant can achieve.

Input

The first line contains two space-separated integers $$$n\ (1\leq n \leq 5000)$$$ and $$$m\ (1\leq m \leq 5000)$$$, representing the number of landmarks and the number of roads in Harbin, respectively.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n\ (1\leq a_i\leq 10^8)$$$, representing the happiness value of each landmark.

The following $$$m$$$ lines, each contains two space-separated integers $$$u_i$$$ and $$$v_i\ (1\leq u, v\leq n)$$$, indicating a road connecting the landmarks $$$u_i$$$ and $$$v_i$$$. It is guaranteed that each road is unique.

Output

Output a single integer representing the maximum total happiness value Paulliant can achieve from his photography tour.

Examples
Input
4 5
5 6 3 4
1 2
1 3
2 3
2 4
3 4
Output
18
Input
7 10
6 7 8 6 1 7 10
1 2
1 5
2 3
2 5
3 5
3 6
3 7
4 5
4 6
5 6
Output
34