马里奥发现自己身处一个富裕的街区。街道上有 $N$ 栋房子，每栋房子里有 $S_i$ 颗星星，其中 $i \in [1, N]$。

他得到了 $K$ 个容量无限的麻袋，用来装偷来的星星。他可以从每栋房子里拿走任意数量的星星。然而，来自不同房子的星星不能和睦相处。因此，来自不同房子的星星不能放在同一个麻袋里。但是，马里奥可以将来自同一栋房子的星星分装在多个麻袋中。如果马里奥认为有必要，他也可以让某些麻袋保持为空。

一旦马里奥完成了抢劫，他会遇到库巴（Bowser），库巴会抢走他恰好一半的麻袋。库巴当然会抢走装有最多星星的那些麻袋。知道这一点后，马里奥有两个目标。他的首要任务是最大化他最终保留的星星数量。在最大化该值 $M$ 之后，他的次要任务是确保在所有能让马里奥保留 $M$ 颗星星的抢劫方案中，库巴抢走的星星数量最少。

例如，在第一个样例中，马里奥可以从第 2、6 和 9 栋房子各偷走 10 颗星星，并从第 8 栋房子偷走 9 颗星星。库巴会抢走装得最满的两个麻袋（共 20 颗星星），而马里奥将保留 19 颗星星。请注意，19 颗星星是马里奥可能获得的最大星星数量，而 20 则是所有能让马里奥获得 19 颗星星的方案中，库巴抢走的最小星星数量。

然而，在第二个样例中，马里奥会将第 2 栋房子的 30 颗星星平分到他的三个麻袋中（每个 10 颗），然后在第四个麻袋中装入第 3 栋房子的 10 颗星星。库巴会抢走其中的 20 颗星星，同样留给马里奥 20 颗星星。

输出两个整数，分别代表马里奥最终能保留的最大星星数量，以及他必须给库巴的最小星星数量。

输入格式

第一行包含两个空格分隔的整数：$N$ 和 $K$（$1 \le N, K \le 1\,000$）。保证 $K$ 是偶数。

第二行包含 $N$ 个整数 $S_i$（$0 \le S_i \le 1\,000$），每个数字代表对应房子里的星星数量。

输出格式

输出一行，包含两个整数，依次代表马里奥最终能保留的最大星星数量，以及他必须给库巴的最小星星数量。

样例

输入样例 1

10 4
3 12 4 6 1 10 8 9 18 0

输出样例 1

19 20

输入样例 2

3 4
9 30 11

输出样例 2

20 20