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:
If everyone played optimally, find the maximum & minimum score Sam can have if he start's the game first or second.
Input Format:
Output Format:
Print two space-separated integers denoting the maximum & minimum score Sam can have in the game.
Constraints:
1≤N,M≤1051≤A[i]≤106
Sam plays first
Sam plays second