删除球 - 代码源竞赛平台

题目描述

apiadu 有 $n$ 个球。第 $i$ 个球的颜色编号为 $a_i$，删除这个球需要支付 $c_i$ 枚金币。

apiadu 可以删除任意数量的球，但删除后必须至少保留一个球。他希望任意两个保留下来的球的颜色编号之差的绝对值都不超过 $k$。

形式化地，若球 $i$ 和球 $j$ 均未被删除，则必须满足

$$|a_i-a_j|\le k.$$

对于任意整数 $x$，其绝对值 $|x|$ 定义为

$$|x|= \begin{cases} x,&x\ge 0,\\ -x,&x<0. \end{cases}$$

请计算满足要求所需支付的最小总金币。

输入格式

第一行包含两个整数 $n,k$，分别表示球的数量和允许的最大颜色编号差。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 个球的颜色编号。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示删除第 $i$ 个球所需支付的金币。

输出格式

输出一个整数，表示满足要求所需支付的最小总金币。

样例

5 1
1 1 2 2 5
4 2 3 6 1

1

4 3
1 1 2 4
8 3 5 7

0

6 1
1 1 1 2 5 6
1 1 1 1 100 100

4

样例解释

对于第一个样例，删除颜色编号为 $5$ 的球后，剩余球的颜色编号均为 $1$ 或 $2$，任意两个颜色编号之差都不超过 $1$。此次删除需要的金币为 $1$，且不存在金币更小的方案。

对于第二个样例，所有球中最大的颜色编号为 $4$，最小的颜色编号为 $1$，二者之差为 $3$，没有超过 $k$，因此不需要删除任何球。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$
$1$	$20$	$20$
$2$	$30$	$2000$
$3$	$50$	$2 \times 10^5$

对于 $100\%$ 的数据，$1\le n\le 2 \times 10^5$，$0\le k\le n$，$1\le a_i\le n$，$1\le c_i\le 10^9$。