噜噜的糖果分配

题目描述

在一个阳光明媚的下午，小探险家噜噜和他的好朋友一只羊在森林里发现了一大堆包装精美的糖果袋。每袋糖果的数量不尽相同。它们决定通过一种公平（或许吧？）又有趣的方式来分配这些糖果。

森林里共有 $N$ 袋糖果，每袋糖果的数量都印在了包装上。噜噜和一只羊将轮流从这些糖果中选取。作为发现者，噜噜享有优先选择权，即噜噜先选。

每一轮，当前轮到的人都会从当前剩下的糖果中，选择糖果数量最多的那一袋拿走。

他们一共要进行 $M$ 轮选择（也就是说，总共会拿走 $M$ 袋糖果）。如果 $M$ 是奇数，噜噜会比一只羊多拿一袋；如果 $M$ 是偶数，他们拿的袋数相同。

请你计算，当 $M$ 轮选择结束后，噜噜和一只羊分别获得了多少颗糖果。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示糖果的总袋数和他们总共要选取的袋数。 第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$，表示每袋糖果的数量。

输出格式

输出一行，包含两个整数，分别表示噜噜获得的糖果总数和一只羊获得的糖果总数，两个数字之间用一个空格隔开。

样例 #1

样例输入 #1

5 3
10 20 5 15 25

样例输出 #1

40 20

样例解释 #1

初始糖果袋数量为: $[10, 20, 5, 15, 25]$。总共选取 $M=3$ 袋。

1. 噜噜的回合 (第1轮): 当前可选糖果中最多的是 $25$。噜噜选择 $25$。
   • 噜噜获得: $25$
   • 一只羊获得: $0$
   • 剩余糖果: $[10, 20, 5, 15]$
2. 一只羊的回合 (第2轮): 当前可选糖果中最多的是 $20$。一只羊选择 $20$。
   • 噜噜获得: $25$
   • 一只羊获得: $20$
   • 剩余糖果: $[10, 5, 15]$
3. 噜噜的回合 (第3轮): 当前可选糖果中最多的是 $15$。噜噜选择 $15$。
   • 噜噜获得: $25 + 15 = 40$
   • 一只羊获得: $20$
   • 剩余糖果: $[10, 5]$

共选取了 $3$ 袋，噜噜获得 $40$ 颗，一只羊获得 $20$ 颗。

样例 #2

样例输入 #2

4 4
10 10 10 10

样例输出 #2

20 20

样例解释 #2

初始糖果袋数量为: $[10, 10, 10, 10]$。总共选取 $M=4$ 袋。

1. 噜噜 (第1轮): 选 $10$。噜噜: $10$, 羊: $0$。剩余: $[10, 10, 10]$
2. 一只羊 (第2轮): 选 $10$。噜噜: $10$, 羊: $10$。剩余: $[10, 10]$
3. 噜噜 (第3轮): 选 $10$。噜噜: $20$, 羊: $10$。剩余: $[10]$
4. 一只羊 (第4轮): 选 $10$。噜噜: $20$, 羊: $20$。剩余: $[]$

共选取了 $4$ 袋，噜噜获得 $20$ 颗，一只羊获得 $20$ 颗。

说明/提示

【数据范围与约定】

子任务编号	$N$ 的范围	$M$ 的范围	$a_i$ 的范围	分值比例	特殊约定
1	$N \le 10$	$M \le N$	$1 \le a_i \le 100$	20%
2	$N \le 1000$		$1 \le a_i \le 10^5$	30%
3	$N \le 10^5$		$1 \le a_i \le 10^9$	50%	糖果总数可能超过32位整数

对于所有数据：

• $1 \le M \le N \le 10^5$。
• $1 \le a_i \le 10^9$。