D-修改后的和_牛客小白月赛74

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛面前有一个由 $n$ 个整数组成的数组 $A_1,A_2,...,A_n$ 。

牛牛打算对这个数组进行若干次操作。

每次操作牛牛可以选择 $A_1,A_2,...,A_n$ 中的任意一个非负整数，记所选数的下标为 $k$ 。然后牛牛会把 $A_k,A_{k+1},...,A_n$ 都减少 $A_k$ 。

牛牛想知道他对这个数组进行恰好 $m$ 次操作后，数组中所有数的和最少是多少。

输入描述:

本题采用多组案例输入，第一行一个整数 $T$ 代表案例组数。

每组案例中，第一行输入两个空格分隔的整数 $n\ m$ 。

接下来一行输入 $n$ 个由空格分隔的整数代表： $A_1,A_2,...,A_n$ 。

保证：

$1 \leq n,m \leq 10^5$

$-10^6 \le A_i \le 10^6$

单个测试点中所有案例 $n$ 的和不超过 $2\times 10^5$

单组案例的 $A_1,A_2,...,A_n$ 中至少有一个非负整数

输出描述:

对于每组案例，输出一行一个整数代表牛牛在进行恰好 m 次操作之后数组中所有数的和的最少值。

示例1

输入

复制

2
5 10000
-9 0 -3 -1 -10000
5 3
-10 4 9 -2 0

输出

复制

-10013
-42

说明

第一组案例只能不断地选择  所以总和不变。 
第二组案例一组最优选择是 [] 
数组的变化是： [-10,4,9,-2,0] --> [-10,4,0,-11,-9] --> [-10,0,-4,-15,-13] --> [-10,0,-4,-15,-13]  第二组理论上更好的方案是选择 [] 
但是由于选择  时其是负数，所以这组方案不可以选择。