主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 E: 余神的rp机

问题 E: 余神的rp机

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

题目描述

经过一个暑假的精心研制,余神做出了一台rp机。
但这个机器有一个缺点,它要求恒定的燃料供给,否则核芯就会坏掉。

具体来说,余神需要先给核芯设定一个燃料供给速率 k。
如果某时刻的燃料供给速率大于等于 k,机器就能产生 k 点 rp。
如果某时刻的燃料供给速率小于k,那么就会产生可怕的rp大爆炸。

为了避免rp大爆炸,余神可以在时刻交替的临界点拆下核芯,或者换上一个新核芯。
余神曾经跑赢过香港记者,所以更换核芯的时间可以忽略不计。
出于安全考虑,余神不能再次使用被换下的核芯。

由于网络赛就要到了,余神决定涨一波rp。
余神一共只有 m 个核芯,好在他计算出了接下来 n 时刻的燃料供给速率。
问余神最大能增加多少的 rp。

输入

第一行 T 表示有 T 组数据。
每组数据
    第一行 n m (1 <= n <= 500, 1 <= m <= 50)
    第二行 n 个自然数,表示 t 时刻的供给速率 s[t]。(0<= s[t] <= 500)

输出

每组数据
    一行,一个整数,最大能增长的 rp 值。

样例输入

3
10 1
3 3 3 1 1 1 1 3 3 3
10 2
3 3 3 1 1 1 1 3 3 3
10 3
3 3 3 1 1 1 1 3 3 3

样例输出

10
18
22

提示

样例1

t = 1, k = 1

rp = 1 * 10 = 10



样例2

t =  1, k = 3

t = 8, k = 3

rp = 3 * 3 + 3 * 3 = 18



样例3

t = 1, k = 3

t = 4, k = 1

t = 8, k = 3

rp = 3 * 3 + 1 * 4 + 3 * 3 = 22

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