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\)