Distanced (distanced, 2s, 512M)

Bytelane 上停着 $n$ 辆车。文明城市评比就要开始了，作为 Bytecity 市长的你决定移除一部分车使得街道更文明（也可以什么也不移除）。

一个文明的街道首先应该整齐：车不应该停得过于散乱。我们称两辆车 $x$ 和 $y$ 属于同一个联通块当且仅当它们的距离不超过 $t$（“直接相邻”），或存在车 $c$ 使得 $x$ 和 $c$ 属于同一个联通块且 $c$ 和 $y$ 属于同一个联通块（“间接相邻”）。街道的散乱度为联通块的数量（即两两不属于同一个联通块的车集合的最大可能大小）。

一个文明的街道还应该尽量美观：第 $i$ 辆车有 $a_i$ 的美观度，而街道的美观度是剩余车辆美观度的总和。由于部分车辆可能年久失修，$a_i$ 可能为负。

由于你还没有决定好街道的整齐程度，对于每个 $s \in \{1,2,\cdots,n\}$，你想要知道散乱度不超过 $s$ 的移除方案中美观度的最大值。

输入格式

第一行两个正整数 $n,t$，表示车辆数和直接相邻的距离上限。

第二行 $n$ 个整数 $x_1,x_2,\cdots,x_n$，依次给定每辆车在数轴上的位置。车 $a$ 和车 $b$ 的距离为 $|x_a-x_b|$。

第三行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，依次给定每辆车的美观度。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示散乱度不超过 $i$ 的移除方案中美观度的最大值。

样例输入1

5 2
5 1 2 4 8
5 3 4 -1 1

样例输出1

11 12 13 13 13

要求散乱度不超过 $1$ 时一种最优方案是保留前四辆车。要求散乱度不超过 $2$ 时一种最优方案是保留前三辆车。

样例输入2、样例输出2

见选手文件夹下 ex_distanced2.in 和 ex_distanced2.ans。

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le t\le 10^9$，$|x_i|, |a_i|\le 10^9$，$x_i$ 两两不同。

对于 20% 的数据，$n\le 20$。

对于 40% 的数据，$n\le 400$。

对于 70% 的数据，$n\le 2000$。

对于另外 10% 的数据，$a_i\ge 0$。