问题描述：



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



编程任务：



对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。



Input

测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。



Output

输出最大总费用和最小总费用，用一空格隔开，每个答案一行。



Sample Input

7 3

45 13 12 16 9 5 22



Sample Output

593 1-Problem Descr iption: n heap stones placed around a playground. Now want to stone in order to merge into a pile. Provision for at least selected pile up election k to heap stones merger into a new pile of combined costs for the new pile of stones number. Try to design an algorithm to calculate the maximum total cost and minimum total cost of n heap stones combined into a pile. Programming tasks: For a given n heap stones, programming calculation merged into a bunch of maximum total cost and minimum total cost. Input test data the first row there are two positive integers n and k, n heap stones, each time at least one selected two heap up selected k heap stones merge. The second row has n numbers denote the number of each heap stones. Output Output maximum total cost and minimum total cost, separated by a space, each answer a row. Sample Input 7 3 45 13 12 16 9 5 22 Sample Output 593 199