Get Largest Number

Split the whole array into exactly p non-empty contiguous segments. The cost of a segment is its first element plus its last element; a single-element segment counts that element twice. Output the minimum and the maximum total cost, in that order. The source's second example had them reversed; this site corrects it to 8 12.

输入格式

The first line contains n p; the second line contains the costs. This site uses 1≤n≤200000, 1≤p≤n, costs 1..10^9.

输出格式

Output the minimum cost and the maximum cost, separated by a space.

样例 1

输入：

5 3
1 2 3 2 5

输出：

14 18

样例 2

输入：

4 2
1 2 3 4

输出：

8 12

样例 3

输入：

1 1
5

输出：

10 10

样例说明

The answers are 14 18, 8 12 and 10 10.