题目描述

@Lelzy 有 $n$ 个礼物盒，第 $i$ 个礼物盒的价值为 $a_i$。

现在要选出至多 $k$ 个礼物盒，且至少选择 $1$ 个礼物盒，使得所选礼物盒价值之和最大。

注意，礼物盒价值为任意整数（即包括 $0$ 和负数）。

输入格式

第一行输入两个正整数 $n$、$k$，表示礼物盒的个数和最多选取的礼物盒个数。

第二行输入 $n$ 个整数，第 $i$ 个数表示第 $i$ 礼物盒的价值 $a_i$。

输出格式

输出最大礼物盒价值之和。

输入输出样例 #1

输入 #1

6 3
1 1 4 5 1 4

输出 #1

13

输入输出样例 #2

输入 #2

6 3
-1 -1 -4 -5 -1 -4

输出 #2

-1

说明/提示

对于 $20\%$ 的数据有 $1 \le n \le 20$，$1 \le k \le 5$。

对于另外 $20\%$ 的数据有 $1 \le a_i \le 10^8$。

对于 $100\%$ 的数据有 $1 \le k \le n \le 10^6$，$-10^{8} \le a_i \le 10^{8}$。