题目描述

给出一个长度为 $n$ 数组 $a$，你必须进行 $k$ 次如下操作：

删除当前数组中的第一个元素或者最后一个元素。

求 $k$ 次操作结束后你能得到的数组和的最大值与最小值分别是多少。

注意定义空数组的和为 $0$。

输入格式

从文件 delete.in 中读入数据。

第一行两个正整数 $n,k$，分别表示数组长度与操作次数。

第二行共 $n$ 个整数，表示数组 $a$ 中的元素 $a_1,a_2,...,a_n$。

输出格式

输出到文件 delete.out 中。

一行两个整数表示答案，其中第一个数字表示最大值，第二个表示最小值，两个整数以空格隔开。

样例

输入样例1

5 1
1 2 3 4 5

输出样例1

14 10

输入样例2

5 2
4 5 6 7 1

输出样例2

18 14

数据范围

对于 40% 的测试数据，$1 \le n \le 10^3$，$0 \le k \le 10$。

对于 100% 的测试数据，$0 \le k \le n \le 2\times 10^6$，$|a_i| \le 10^9$，并且 $k \le n$ 始终成立。