Comet OJ

C1059 [HNOI2009]通往城堡之路

内存限制：256 MB 时间限制：1000 ms

题目描述

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

可是，通往城堡的路上出现了一些情况。抽象地说，假象地图在二维平面的第一象限。在每个横轴的 $x$ 位置上有一个高为 $h_x$ 的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。开始时彭大侠在起点（$1,h_1$）处，而城堡的入口在（$n,h_n$）处。彭大侠每次可以从支撑点（$x,h_x$）跳到支撑点（$x+1，h_{x+1}$）。但是彭大侠每次的跳跃能量只有 $d$，也就是说，每次跳跃必须满足条件 $|h_{x+1}-h_n|≤d$。换句话说，如果两个相邻支撑点的纵向落差大于 $d$，那么彭大侠就无法跳跃了！幸运的是，彭大侠还有一个杀手锏。在起点处，他可以花一个金币，把某个支撑点升高 $1$ 个单位，或者降低 $1$ 个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏。

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

输入格式

第一行包含一个整数 $m(m≤5)$，表示问题求解次数。接下来的 $2m$ 行依次表示每次求解的输入数据块。每个输入数据块占 $2$ 行，其中第一行包含两个整数 $n$ 和 $d$，分别表示从起点到城堡入口处必须经过的支撑点数和每次跳跃允许的最大纵向落差，$n$ 和 $d$ 之间用空格隔开，输入数据保证 $2≤n≤5000$，$40≤d≤10^9$；第二行包含用空格隔开的 $n$ 个非负整数 $h_1$、$h_2$、…、$h_n$，其中 $h_i(1≤i≤n)$ 表示第 $i$ 个支撑点的高度，特别地，$h_1$ 表示彭大侠出发时所在支撑点的高度，$h_n$ 表示城堡入口所在支撑点的高度，输入数据保证对所有 $1≤i≤n$ 有 $0≤h_i≤10^9$。

输出

有 $m$ 行，第 $I(1≤I≤m)$ 行表示第 $I$ 次求解时彭大侠到达城堡必须耗费的最少金币数量。若无论怎样使用杀手锏他都无法到达城堡，则输出impossible。输入数据保证答案在 long long 范围之内。

样例

样例输入 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

样例输出 1

6
impossible
4

提示

【样例说明】

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

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

对样例中的第三个输入数据块，$d=2$，这时，把第二个支撑点升高 $1$ 个单位，把第三个支撑点降低 $3$ 个单位就满足条件了。

【数据规模】

$20\%$ $n≤100$

$40\%$ $n≤1000$

$100\%$ $n≤5000$