题目描述

在一个操场的四周摆放着$\red {n}$ 堆石子。现要将石子有次序地合并成一堆。规定每次至少选$\red {2 }$堆最多选$\red {k}$堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将$\red {n}$堆石子合并成一堆的最大总费用和最小总费用。 对于给定$\red {n}$堆石子,编程计算合并成一堆的最大总费用和最小总费用。

输入格式

文件的第$\red {1}$ 行有$\red {2}$ 个正整数$\red {n}$和$\red {k}$，表示有$\red {n}$堆石子，每次至少选$\red {2}$ 堆最多选$\red {k}$堆石子合并。第$\red {2}$ 行有$\red {n}$个数，分别表示每堆石子的个数。

输出格式

程序运行结束时，将计算出的最大总费用和最小总费用输出

样例

输入样例

7 3

45 13 12 16 9 5 22

输出样例

593 199