你和你的船员同伴们正在 The Skeld 号飞船上。然而，在检查中央电力系统时，你发现中央电力系统的一个关键布线装置遭到了破坏。为了防止发动机故障，你必须迅速修复该装置。

该装置由 $N$ 个节点和 $M = \frac{N(N-1)}{2}$ 条导线组成。装置中所有可能的不同节点对之间都连接有一条导线。起初，这 $M$ 条导线中的每一条都恰好贴有一个标签。每个标签都有一个正整数值，不同的标签可能具有相同的值。然而，由于破坏，所有的标签都被从导线上撕下并丢在了地板上。幸运的是，你从地上收集到了所有 $M$ 个标签。现在，为了修复该装置，你必须通过将所有标签重新贴回导线上两次，来触发重启序列。

对于所有导线都贴有标签的装置，我们定义该装置的代价为其最小生成树的代价，即：使得所有节点仅使用给定的导线子集保持连通的导线子集的最小代价。这里，导线集合的代价定义为该集合中所有导线的标签值之和。

重启序列通过以下两个步骤触发：

• 首先，你应该贴上标签以使装置的代价最小。
• 然后，在取下所有标签后，你应该贴上标签以使装置的代价最大。

请计算每次装置的代价。

输入格式

输入的第一行包含一个整数 $N$，表示节点的数量。($2 \le N \le 100$)

输入的第二行包含 $M = \frac{N(N-1)}{2}$ 个正整数 $C_1, C_2, \dots, C_M$，表示 $M$ 个标签的整数值。($1 \le C_i \le 2 \cdot 10^9$)

输出格式

输出单行，包含两个整数。第一个整数应为装置的最小可能代价，第二个整数应为装置的最大可能代价。

样例

输入样例 1

4
5 3 8 8 5 9

输出样例 1

13 16