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$