Sam and Andrea are playing a game today. On a paper, there is a connected graph drawn with \(N\) vertices and \(M\) edges. Every edge has a power assigned to it denoted by an array \(A[i]\).

In every turn, Sam & Andrea have to perform the following one by one:

• Pick an edge which if removed will increase the number of connected components in graph.
• Add the power of the edge picked above to the score.

If everyone played optimally, find the maximum & minimum score Sam can have if he start's the game first or second.

Input Format:

• First line contains two space-separated integers \(N\) and \(M\)
• Next line contains \(M\) space separated integers denoting the array \(A\).
• Next \(M\) lines containts two space-separated integers denoting an edge.

Output Format:

Print two space-separated integers denoting the maximum & minimum score Sam can have in the game.

Constraints:

\(1 \le N, M \le 10^5 \\ 1 \le A[i] \le 10^6\)