题目描述

Lolek 和 Bolek 即将乘飞机出国旅行。当地机场有一个特别的“选择你的飞机”优惠。该优惠的条件如下：

• 旅客可以自行选择乘坐哪架飞机；
• 如果被选中的飞机此刻有 $x$ $(x>0)$ 个空座位，那么该飞机的机票价格为 $x$ 兹罗提（波兰货币单位）。

机场仅有一个售票窗口，窗口前已经排有 $n$ 个旅客。Lolek 和 Bolek 还没有加入队伍，但他们已经在思考，如果所有 $n$ 名旅客都按照本优惠条件购票，机场管理方能够赚得的兹罗提数最多和最少分别是多少？

旅客轮流购票，队伍中的第一人先购票，接下来是第二人，依此类推，直到第 $n$ 人购票。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 1000)$ —— 队伍中的旅客人数以及机场中的飞机数量。
第二行包含 $m$ 个整数 $a_1, a_2, \ldots, a_m$ $(1 \leq a_i \leq 1000)$ —— 其中 $a_i$ 表示在售票窗口开始售票前，第 $i$ 架飞机上的空座位数。

相邻整数之间以空格分隔。保证所有飞机上空座位总数不少于 $n$。

输出格式

输出两个整数，分别表示机场管理方可以赚得的最大和最小兹罗提数。

说明/提示

在第一个样例中，旅客人数等于空余座位总数，因此无论如何选择飞机，管理方能够赚得的总金额是相同的。

在第二个样例中，要获得最大金额，则第 1 人选择第 1 架飞机，第 2 人选择第 2 架飞机，第 3 人选择第 3 架飞机，第 4 人再次选择第 1 架飞机。要获得最小金额，则第 1 人和第 2 人都选择第 1 架飞机，第 3 人和第 4 人都选择第 2 架飞机。

由 ChatGPT 5 翻译

样例

4 3
2 1 1

5 5

4 3
2 2 2

7 6