题意
有 $n$ 个台阶,你可以花费 $a_i$的代价把第 $i(i\in (1, n))$ 个台阶高度加一或减一,求最小代价使得相邻两个台阶的高度差不超过 $d$。
注意:一个台阶的高度可以被减为负数。
输入格式
第一行两个整数 $n,d$。
第二行 $n$ 个整数 $h_i$,表示台阶的初始高度。
第三行 $n-2$ 个整数 $a_2,a_3\cdots a_{n-1}$。
输出格式
输出一个整数表示最小代价对 998244353
取模后的值。
如果无解,则改为输出 Impossible
。
样例
1
3 2
1 5 2
1
2
2
2 1
1 10
Impossible
3-4
数据范围
$n\in [2,5\times 10^5], a_i\in [1, 10^5], h_i\in [1, 10^6], d\in [1, 5], \forall i\in (1, n), h_i\geq h_{i-1}-d-10$。
$Sub1(2):n\leq 5, h_i\leq 10^5$。
$Sub2(10):n\leq 100, h_i\leq 100$。
$Sub3(12):n\leq 1000, h_i\leq 1000$。
$Sub4(30):n\leq 5\times 10^5, h_i\leq 10^5$。
$Sub5(10):h_i\geq h_{i-1}$。
$Sub6(20):h_i\geq h_{i-1}-d$。
$Sub7(16):$ 无特殊性质。