Maximum Sum of a Simple Path in a Graph

You are given an undirected graph with N vertices and M edges. Each vertex i is associated with a value v_i. Your task is to find the maximum sum over all simple paths in the graph. A simple path is defined as a sequence of vertices where each vertex appears at most once, and consecutive vertices are connected by an edge.

The problem can be formally stated as follows:

Given a graph with vertices 1, 2, \ldots, N and edges connecting some pairs, and an array of values values[1 \ldots N], determine

[ \max_{\text{simple path } P} \sum_{i \in P} v_i. ]

Note: The input sizes are small, so an exhaustive search via backtracking or DFS is acceptable.

inputFormat

The input is read from stdin and has the following format:

N M
v1 v2 ... vN
u1 v1
u2 v2
... 
uM vM

Where:

• N is the number of vertices.
• M is the number of edges.
• v1, v2, \ldots, vN are the values associated with each vertex.
• Each of the next M lines contains two integers u and v, representing an edge between vertex u and vertex v.

outputFormat

Output the maximum sum of the values of vertices over all simple paths in the graph to stdout.

Only one integer should be printed, representing this maximum sum.

## sample

4 3
1 2 3 4
1 2
2 3
3 4

10