题目描述

小芳和小苯来参加比赛。比赛共进行 $n$ 轮，获胜者得一分。由于小苯太弱，小芳会赢得每一场比赛的胜利。 给定长为 $n$ 的数组 $c_1, c_2, \dots, c_n$。作为裁判，你可以在第 $i$ 轮时花费 $c_i$ 的代价改变比赛的结果，让小苯获胜。 赞助商希望比赛足够紧张，但又不能改变最终的结果。具体的，给定正整数 $x$，设第 $i$ 轮结束后小芳的分数是 $a_i$，小苯的分数是 $b_i$，要求： $\hspace{23pt}\bullet\,$对于任意 $i\in\left[1, n\right]$，都有 $a_i - b_i \leq x$。 $\hspace{23pt}\bullet\,$$a_n > b_n$。 请你计算，要让赞助商满意，最小的花费是多少？如果永远无法让赞助商满意，请输出 $\texttt{-1}$。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 10^4\right)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入两个整数 $n,x\left(1 \leq n \leq 2\times 10^5;\,1 \leq x \leq n\right)$。 第二行输入 $n$ 个整数 $c_1, c_2, \dots, c_n\left(1 \leq c_i \leq 10^9 \right)$。官方中文

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。官方中文

输出格式

对于每组测试数据，新起一行。官方中文

如果永远无法让赞助商满意，请输出 $\texttt{-1}$；否则输出一个整数，代表可能的最小花费。官方中文