欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1062. -- Black King Bar

1062: Black King Bar

时间限制: 1 Sec  内存限制: 128 MB
提交: 186  解决: 53
[提交][状态][讨论版]

题目描述

For kazmodon!

——A DotA hero using BKB


一天,lw梦见自己在打dota,然而对面是一个加强过的卡尔!于是,他每次都被n个技能瞬间秒杀。愤怒的lw决定买BKB,来加强生存力。

由于加强过的卡尔是电脑操作的,他每次看见lw时,只会以1毫秒的时间间隔连续放n个技能,第i个技能造成ki点伤害。如果某个技能没有成功放出来,他也不会试图再次释放该技能。已知lw的BKB可以为他提供t毫秒的魔免时间(即,能抵挡连续的t个技能),那么BKB至多能降低多少伤害呢?

输入

多组数据(不超过10组)。

每组数据,第一行2个整数n、t,第二行n个整数k1,k2,...,kn,用空格分割。

数据保证1<=n<=100000,1<=t<=10000,0<=ki<=1000。

输出

输出1行,一个整数,表示BKB能避免的最大伤害。

样例输入

5 3
1 2 3 4 5

样例输出

12

提示

对于样例,最优策略显然是用BKB抵挡掉后3个技能。

来源

[提交][状态][讨论版]