Find Partition Cost

Split the array into exactly k non-empty contiguous segments; each segment costs its first element plus its last element, and a single-element segment counts that element twice. Output the minimum and maximum total cost.

输入格式

The first line contains n k (1≤k≤n≤200000), and the second line contains n positive integers (1..10⁹).

输出格式

Output the minimum total cost and the maximum total cost.

样例 1

输入：

5 3
1 2 3 2 5

输出：

14 18

样例 2

输入：

1 1
7

输出：

14 14

样例 3

输入：

2 2
1 2

输出：

6 6

样例说明

Example 1: the fixed cost of the first and last elements is 6, and the cut weights are 3, 5, 5, 7; the minimum takes 3 and 5 for 14, and the maximum takes 7 and 5 for 18. Example 2: both ends of the single-element segment are 7, for a cost of 14. Example 3: the array must be split into [1] and [2], for a cost of 2+4=6.