Description

It is said that the princess is imprisoned in the castle. Peng the Hero is determined: no matter how many obstacles lie ahead, no matter how powerful the guards in the castle are, no matter whether the princess might be captured again after being rescued, and no matter whether the princess is beautiful or will fall for him, he will march toward the castle without hesitation.

However, something has happened on the road to the castle. Abstractly, imagine the map lies in the first quadrant of the 2D plane. At each horizontal position $x$ there is a support point of height $h_x$. If Peng the Hero fails to land on a support point, he will fall and perish on the way.

Initially, Peng the Hero is at the starting point $(1, h_1)$, and the castle entrance is at $(n, h_n)$. Each time, Peng the Hero can jump from support point $(x, h_x)$ to support point $(x+1, h_{x+1})$. But each jump only has energy $d$, that is, every jump must satisfy $|h_{x+1} - h_x| \le d$. In other words, if the vertical difference between two adjacent support points is greater than $d$, Peng the Hero cannot jump! Fortunately, he has a trump card.

At the starting point, he can spend one coin to increase the height of some support point by $1$ unit, or decrease it by $1$ unit. However, the heights of the support points at the starting point and at the castle entrance cannot be changed, and once he leaves the start, Peng the Hero can no longer use this trump card.

Peng the Hero is told that $100$ coins can be exchanged for one unit of life. Therefore, he wants to save as many units of life as possible by spending as few coins as possible.

He finally found you, a helpful expert. Please help him plan so that he reaches the castle while spending the fewest coins.

Input Format

The first line contains an integer $m$ ($m \le 5$), the number of test cases. The following $2m$ lines describe the input data blocks for each test case in order. Each test case occupies $2$ lines:

• The first line contains two integers $n$ and $d$, representing the number of support points that must be traversed from the start to the castle entrance, and the maximum allowed vertical difference per jump, respectively, separated by a space. It is guaranteed that $2 \le n \le 5000$, $0 \le d \le 10^9$.
• The second line contains $n$ non-negative integers $h_1, h_2, \dots, h_n$ separated by spaces, where $h_i$ ($1 \le i \le n$) is the height of the $i$-th support point. In particular, $h_1$ is the height at the start and $h_n$ is the height at the castle entrance. It is guaranteed that for all $1 \le i \le n$, $0 \le h_i \le 10^9$.

Output Format

Output $m$ lines. The $I$-th line ($1 \le I \le m$) contains the minimum number of coins Peng the Hero must spend to reach the castle in the $I$-th test case. If he cannot reach the castle no matter how he uses the trump card, output impossible. It is guaranteed that the answer fits within the int64 range.

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

Hint

For the first sample input block, $d = 2$. Lower the third support point by $3$ units, lower the sixth by $1$ unit, and raise the seventh by $2$ units. The sequence becomes: 4 5 7 6 6 8 6 7 9 8. Now the vertical difference between any adjacent support points does not exceed $2$, so Peng the Hero can reach the castle!

For the second sample input block, $d = 1$. No matter how you adjust the height of the second support point, you cannot make every adjacent vertical difference at most $1$.

For the third sample input block, $d = 2$. Raising the second support point by $1$ unit and lowering the third by $3$ units suffices.

Constraints

• For $20\%$ of the testdata, $n \le 100$.
• For $40\%$ of the testdata, $n \le 1000$.
• For $100\%$ of the testdata, $n \le 5000$.

Translated by ChatGPT 5