简要题意.

对于给定的区间列 $[s_1, e_1], [s_2, e_2], \dots, [s_N, e_N]$，定义区间图是无向图 $(V,E)$，其中 $V = \{1, 2, \dots, N\}$，$E = \{(i, j) \mid [s_i, e_i] \cap [s_j, e_j] \ne \varnothing\}$。

给定 $N, K$ 和 $N$ 个区间 $[s_i, e_i]$，每个区间有权值 $w_i$，要求删除若干区间使得剩下的区间构成的区间图的各连通块大小不超过 $K$。
问删除的区间的最小权值和。

$K \le N \le 2500$，$e_i \le 10^9$，$1 \le w_i \le 10^9$。

区间图的一个连通块一定可以表为一个区间。反过来，可以发现我们只需要将整个数轴划分为若干区间，在各区间中选择包含在其中的前 $K$ 大个区间即可。不难发现这样一定可以计算出答案。于是，要想将计算转移代价的过程优化到 $O(N^2 \log N)$ 或 $O(N^2)$ 是很容易的。