Lolek 和 Bolek 即将乘飞机出国旅行。当地机场有特别的“选择您的飞机”优惠。优惠条件如下:
- 由乘客选择乘坐的飞机;
- 如果所选飞机在给定时刻有 x (x > 0) 个空座位,则此类飞机的机票费用为 x 兹罗提(波兰货币单位)。
机场唯一的售票处前面已经排起了n个旅客的队列。 Lolek和Bolek还没有排队,但他们已经在想,如果所有n名乘客都按照此优惠条件购买机票,机场管理部门最多可以获得多少兹罗提?
乘客依次买票,队列中的第一个人先买票,然后是第二个人,依此类推,直到第n个人。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 相应地,队列中的乘客数量和机场中的飞机数量。下一行包含 m 个整数 a1, a2, ..., am (1 ≤ ai ≤ 1000) — ai 代表售票处开始售票前第 i 个飞机上的空座位数。
行中的数字由空格分隔。保证总共至少有n个空座位。
输出
打印两个整数 - 机场管理部门可以相应赚取的最大和最小兹罗提数。
示例
输入 #1
4 3 2 1 1
输出 #1
5 5
输入 #2
4 3 2 2 2
输出 #2
7 6
注意
在第一个测试样本中,乘客数量等于空座数量,因此无论选择何种方式选择飞机,管理部门都将获得相同的金额。
在第二个样本中,如果队列中的第 1 个人购买了前往第 1 架飞机的机票,第 2 个人购买了前往第 2 架飞机的机票,第 3 个人购买了前往第 3 架飞机的机票,第 4 个人购买了前往第 1 架飞机的机票,则总和最大化。如果队列中的第一个人购买了第一架飞机的机票,第二个人购买了第一架飞机的机票,第三人购买了第二架飞机的机票,第四个人购买了第二架飞机的机票,则该金额将最小化。