题目描述

给定一个长度为 n 的整数序列 $a_1,a_2,…,a_n$，你需要从中恰好取出 k 个数，使得它们的和最大。 请输出这个最大和。

输入格式

第一行包含两个整数 n 和 k。 第二行包含 n 个整数 $a_1,a_2,…,a_n$。

输出格式

输出一个整数，表示从 n 个数中取出 k 个数后能得到的最大和。

5 2
1 2 3 4 5

9

6 3
-1 5 -2 4 -3 6

15

4 4
-1 -2 -3 -4

-10

数据范围

• $1 \leq k \leq n \leq 2000$
• $-10^9 \leq a_i \leq 10^9$