该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

大学时，$\texttt{chase}$ 经常在训练的时候给小胖读假题，腹黑的小胖决定报复$\, \texttt{chase}$。经过含辛茹苦的努力之后，小胖成功转型为一名道路设计师，并负责设计$\, \texttt{chase} \,$下班必经之路。

$\texttt{chase}\,$下班的道路分为 $n$ 段，标记为​ $1$  ~  $n$，每段路的海拔为 $a_i$ 米。

小胖想在路上制造至少 $k$ ​个坎（坎定义为：$i$ 处的路面海拔均高于 $i-1,i+1$ 两处的海拔，则称 $i$ 处为一个坎），但是小胖每次操作只能将某段路的海拔降低 $1$ 米。

前面说了小胖很懒，所以现在小胖请你帮忙算算她最少需要操作多少次，能形成至少 $k$ 个坎。

产生这个想法之后小胖觉得自己非常邪恶，所以形成至少 $k$ 个坎之后小胖就满意了。

你可以认为路段 $1$ 只和路段 $2$ 相邻，降低路段 $2$ 的海拔就能在 $1$ 处形成一个坎，路段 $n$ 只和路段 $n-1$ 相邻，降低路段 $n-1$ 的海拔就能在 $n$ 处形成一个坎。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来每组数据两行，

第一行两个正整数 $n,k$，分别表示路分为 $n$ 段和小胖想制造至少 $k$ 个坎，

第二行 $n$ 个正整数 $a_i$ 表示每段路的海拔。

$1 \leq T \leq 100$，$1 \leq k \leq n \leq 5000$，$1 \leq a_i \leq 10^5$，$\sum{n} \leq 5000$。

输出格式

每组数据输出一行，若小胖无法制造至少 $k$ 个坎则输出 $-1$，否则输出最小的操作次数。

样例

3
5 3
1 2 3 4 5
5 4
6 6 6 6 6
5 2
2 5 3 4 1

4
-1
0

提示

对于样例 $1$，让第 $2$ 段和第 $4$ 段道路的海拔减少 $2$ 米，即操作 $4$ 次即可形成 $1,3,5$ 这 $3$ 处坎。

对于样例 $2$，无论如何都不能形成 $4$ 个坎。

对于样例 $3$，已经有第 $2$ 处和第 $4$ 处两个坎了，小胖非常满意。