M-终极考验_华中农业大学第十五届程序设计竞赛（新生赛）同步赛

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

题目描述

小 W 面前有 $n$ 个石柱，第 $i$ 个石柱的高度为 $h_i$ 米。小 W 拿到了一个整数 $x$ 。小 W 可以耗费 $1$ 点能量完成以下操作：

选择 $i$ ( $1 \leq i \leq n$ )，令 $L = i$ ， $R = \min\{i + x - 1, n\}$ ，对于所有满足 $L \leq j \leq R$ 的 $j$ ，令 $h_j \leftarrow h_j + 1$ 。换言之，选择一个石柱，小 W 可以将它及其后面的共 $x$ 个石柱升高 $1$ 米。

小 W 希望最后石柱的高度单调不降。请求出小 W 耗费能量的最小值。

输入包含多组数据。

首先输入一行一个整数  ()，表示数据的组数。

对于每组数据，首先输入一行两个整数 ,  ()，分别表示石柱的数量和小 W 拿到的整数。

接下来输入一行  个整数  ()，其中  表示第  个石柱的初始高度。

保证对于一个测试点的所有数据， 的和不超过 。

对于每组数据，输出一行一个整数，表示最少需要的能量。可以证明，在有限次操作内，一定可以使得所有石柱的高度单调不降。

示例1

复制

3
5 3
10 8 12 9 15
4 1
4 3 2 1
6 2
1 3 6 10 15 21

复制

5
6
0

在第一组数据中，小 W 可以首先选择 ，重复  次操作，耗费  点能量，石柱高度变为 ；然后选择 ，重复  次操作，耗费  点能量，石柱高度变为 。可以证明，没有耗费能量更少的操作方案。

在第三组数据中，不需要任何操作。