[HNOI2009]通往城堡之路

听说公主被关押在城堡里，彭大侠下定决心：不管一路上有多少坎坷，不管城堡中的看守有多厉害，不管救了公主之后公主会不会再被抓走，不管公主是否漂亮、是否会钟情于自己，他将义无反顾地朝着城堡前进。

可是，通往城堡的路上出现了一些情况。抽象地说，假想地图在二维平面的第一象限，在横轴的每个 $x$ 位置上有一个高为 $h_x$ 的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。

开始时彭大侠在起点 $(1, h_1)$ 处，而城堡的入口在 $(n, h_n)$ 处。彭大侠每次可以从支撑点 $(x, h_x)$ 跳到支撑点 $(x+1, h_{x+1})$，但是他每次的跳跃能量只有 $d$，也就是说每次跳跃必须满足条件

$$|h_{x+1}-h_x|\le d .$$

换句话说，如果两个相邻支撑点的纵向落差大于 $d$，那么彭大侠就无法跳跃了！

幸运的是，彭大侠还有一个杀手锏：在起点处，他可以花一个金币，把某个支撑点升高 $1$ 个单位，或者降低 $1$ 个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点，彭大侠就无法使用该杀手锏。

彭大侠被告知 $100$ 个金币可兑换一单位生命，于是他希望通过少花金币来保存更多单位的生命。他终于找到了你这位热心的高手，请你帮他规划一下，以便耗费尽量少的金币来到达城堡。

输入格式

第一行包含一个整数 $m$，表示问题求解次数。

接下来的 $2m$ 行依次表示每次求解的输入数据块，每个输入数据块占 $2$ 行：

• 第一行包含两个用空格隔开的整数 $n$ 和 $d$，分别表示从起点到城堡入口处必须经过的支撑点数和每次跳跃允许的最大纵向落差；
• 第二行包含用空格隔开的 $n$ 个非负整数 $h_1, h_2, \dots, h_n$，其中 $h_i$ 表示第 $i$ 个支撑点的高度。特别地，$h_1$ 表示彭大侠出发时所在支撑点的高度，$h_n$ 表示城堡入口所在支撑点的高度。

输出格式

输出共 $m$ 行，第 $I$ 行（$1\le I\le m$）表示第 $I$ 次求解时彭大侠到达城堡必须耗费的最少金币数量。

若无论怎样使用杀手锏他都无法到达城堡，则输出 impossible。

样例输入

3
10 2
4 5 10 6 6 9 4 7 9 8
3 1
6 4 0
4 2
3 0 6 3

样例输出

6
impossible
4

样例解释

对第一个输入数据块，$d=2$，把第三个支撑点降低 $3$ 个单位、第六个支撑点降低 $1$ 个单位、第七个支撑点升高 $2$ 个单位，原序列变成 $4\ 5\ 7\ 6\ 6\ 8\ 6\ 7\ 9\ 8$。这时任意相邻支撑点的纵向落差都没有超过 $2$，彭大侠可以到达城堡，共花费 $6$ 个金币。

对第二个输入数据块，$d=1$，这时不管怎样调节第二个支撑点的高度，都无法使任意相邻支撑点的纵向落差不超过 $1$。

对第三个输入数据块，$d=2$，把第二个支撑点升高 $1$ 个单位、第三个支撑点降低 $3$ 个单位就满足条件了，共花费 $4$ 个金币。

数据范围

• $m\le 5$；
• $2\le n\le 5000$，$0\le d\le 10^9$；
• 对所有 $1\le i\le n$ 有 $0\le h_i\le 10^9$；
• 对于 $20\%$ 的数据，$n\le 100$；
• 对于 $40\%$ 的数据，$n\le 1000$；
• 对于 $100\%$ 的数据，$n\le 5000$；
• 输入数据保证答案在 $64$ 位整数范围之内。

来源与许可

本题为 HNOI 2009 试题「通往城堡之路」，题面与测试数据整理自 BZOJ 1484。

样例 1

输入

3
10 2
4 5 10 6 6 9 4 7 9 8
3 1
6 4 0
4 2
3 0 6 3

输出

6
impossible
4