3006 - 赚钱

最近崂山区要开展一个特殊的市集,这里不仅是个交易的场所,更像是一个充满故事的宝物集市。市集中摆放着 n 件的物品,每件物品都有自己的编号,编号为 i 的物品标价为 a_i 。这里的物品标价很独特,既有正值也有负值,正值代表买家需要支付的金额,而负值则是卖家为了快速转手物品愿意支付给买家的额外费用。

由于小明的背包空间有限,最多只能携带 m 件物品,他需要在众多物品中做出明智的选择,以确保能够从市集中获得最大的经济收益。

此时,小明希望得到你的帮助,来策划一个既实用又高效的购买方案,在遵守购买数量上限的同时,需要考虑如何从各个摊位中精选物品,使得他赚取的钱尽可能的多,并告知他最多可以赚多少钱。

输入

第一行,两个整数 n, m ,分别表示物品的个数以及最多能携带的物品数量。

第二行, n 个空格隔开的整数,第 i 个整数 a_i 为第 i 件物品的价格。

输出

共一行,一个数,表示小明最多赚到的钱数。

样例

输入

5 2
-2 -6 9 1 4
6 1
9 0 1 2 8 4

输出

8
0

提示

数据范围

对于 50\% 的数据,满足 1 \leq m \leq n \leq 10^3−10^3 \leq a_i \leq 10^3
对于 100\% 的数据,满足 1 \leq m \leq n \leq 10^6−10^6 \leq a_i \leq 10^6

样例解释

对于样例 1 :购买第一个物品和第二个物品一共可以赚 8 元。
对于样例 2 :购买第二个物品可以赚 0 元。

来源

奇遇编程
2024年青岛市崂山区编程竞赛小学组第二题

题目参数

时间限制 1 秒
内存限制 32 MB
提交次数 0
通过人数 0
统计

上一题 下一题