题目内容

小蓝正在部署 $n$ 台无线设备。每台设备都有一个原始工作频率 $f_i$ 和对应的功耗 $p_i$。

由于频率相近的设备可以相互兼容，若两台设备的原始频率之差不超过 $K$，即 $|f_i - f_j| \le K$，则其中一台设备可以切换为另一台设备的频率来运行。每台设备最终必须选择一个已经存在的频率 $t$（即 $t$ 等于某台设备的原始频率），且该频率与自身原始频率满足 $|f_i - t| \le K$。设备在频率 $t$ 下运行的实际功耗为该频率上所有设备功耗的最小值，即 $\min\{ p_j \mid f_j = t \}$。

请你计算，在所有设备都完成频率分配后，全部设备的最小总功耗。

约束条件

• 设备数量 $n$ 不超过 $10^5$。
• 频率兼容参数 $K$ 不超过 $10^6$。