题意

有 $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):$ 无特殊性质。