P17887 Rain after Summer

[NOIP 2018 普及组] 摆渡车 加强版

给定一个长度为 $n$ 的**单调不降**正整数序列 $a_1,a_2,\ldots,a_n$，以及一个整数 $m$。 定义一个整数序列 $b_1,b_2,\ldots,b_n$ 是好的，当且仅当满足以下条件： 1. 对所有 $1\le i\le n$，有 $b_i\ge a_i$； 2. 将序列 $b$ 按升序排序，记排序后的结果为 $c_1\le c_2\le\cdots\le c_n$，则对于所有 $2\le i\le n$，都有 $c_i=c_{i-1}$ 或 $c_i-c_{i-1}\ge m$。 求所有好的序列 $b$ 中，$\sum_{i=1}^{n}b_i$ 的最小值。

**本题包含多组测试数据。** 输入的第一行包含一个整数 $T$，表示测试数据组数。 接下来依次输入 $T$ 组测试数据。对于每组测试数据： - 第一行包含两个正整数 $n,m$。 - 第二行包含 $n$ 个单调不降的整数 $a_1,a_2,\ldots,a_n$。

对于每组测试数据，输出一行一个非负整数，表示所有好的序列 $b$ 中，$\sum_{i=1}^{n}b_i$ 的最小值。

**【数据范围】** **本题采用捆绑测试。** - Subtask 1（10pts）：$m,a_i,\sum n\le 500$。 - Subtask 2（25pts）：$\sum n\le 5000$。 - Subtask 3（20pts）：$\sum n\le 1.5\times 10^5$。 - Subtask 4（20pts）：$\sum n\le 3\times 10^5$。 - Subtask 5（25pts）：$\sum n\le 10^6$。 对于所有数据，保证 $1\le n,\sum n\le 10^6,1\le a_i,m\le 10^9$，序列 $a$ 单调不降。