#P2397. 数列

    ID: 1440 传统题 1000ms 128MiB 尝试: 38 已通过: 14 难度: 8 上传者: 标签>CF2400提高+/省选-有限候选集缩减离散化线性 DP单调队列优化 DP滚动数组

数列

题目描述

给定一个长度为 nn 的数列 ai(1≤i≤n)a_i(1\le i\le n),需要生成一个数列 bi(1≤i≤n)b_i(1\le i\le n),每个位置的得分为 abs(bi−ai)abs(b_i-a_i),总得分为各个位置得分的总和,要求 abs(bi−bi+1)≤dabs(b_i-b_{i+1})\le d,a1=b1a_1=b_1,an=bna_n=b_n。使得总得分最小。

输入格式

本题含有多组数据

第一行数据组数 tt。

接下来对于每组数据:

第一行两个整数 n,dn,d;

第二行 nn 个整数 aia_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

数据规模与约定

对于所有数据,1≤n≤1001\le n\le 100,1≤d≤1091\le d\le 10^9,1≤ai≤1091\le a_i\le 10^9。