题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「회의실」

有 $K$ 个会议室，$N$ 个会议需要使用这些会议室。每个会议从 $1$ 到 $N$ 编号。会议 $i$ 的开始时间为 $s_{i}$，结束时间为 $e_{i}$，违约金为 $w_{i}$。

这些会议室有一些特殊的规则。会议 $i$ 和会议 $j$ 满足以下任一条件时，称它们是相关会议：

• 两个时间段 $\left[s_{i}, e_{i}\right]$ 和 $\left[s_{j}, e_{j}\right]$ 有重叠（即使只有开始或结束时间重叠），则 $i$ 和 $j$ 是相关会议。
• 两个时间段 $\left[s_{i}, e_{i}\right]$ 和 $\left[s_{j}, e_{j}\right]$ 没有重叠，但另一个会议 $c$ 与 $i$ 相关，并且 $\left[s_{c}, e_{c}\right]$ 和 $\left[s_{j}, e_{j}\right]$ 有重叠（即使只有开始或结束时间重叠），则 $i$ 和 $j$ 是相关会议。

会议可能会被取消，因此上述定义仅适用于未取消的会议。也就是说，原本相关的两个会议，可能因为某些会议被取消而不再相关。

未取消的会议必须分配到一个会议室。所有相关的会议必须分配到不同的会议室。例如，三个会议 $[1,3],[3,5],[5,7]$，尽管 $[1,3]$ 和 $[5,7]$ 之间没有重叠，但仍需要分配三个会议室，而不是两个。由于会议室只有 $K$ 个，因此可能需要取消一些会议。取消会议 $i$ 需要支付违约金 $w_{i}$，因此我们希望通过合理选择取消的会议，最小化支付的违约金总额。

下图展示了 $5$ 个会议 $[1,4],[3,6],[5,8],[7,10],[9,12]$，每个会议的违约金依次为 $1,2,5,2,1$。假设有 $2$ 个会议室。左图中，通过取消会议 $[5,8]$ 满足条件，此时违约金为 $5$。右图中，通过取消会议 $[3,6]$ 和 $[9,12]$ 满足条件，此时违约金为 $3$。综合所有情况，最小违约金总额为 $3$。

实现细节

你需要实现以下函数：

long long int min_charge(int K, vector<int> S, vector<int> E, vector<int> W);

• 该函数只会被调用一次。
• 参数 $K$ 是会议室的数量。
• 参数 $S$、$E$、$W$ 的长度均为 $N$。
• 会议 $i+1$ $(0 \leq i \leq N-1)$ 的开始时间为 $S[i]$，结束时间为 $E[i]$，违约金为 $W[i]$。
• 该函数返回在满足条件的情况下，取消会议所需支付的最小违约金总额。

注意，提交的代码中不应包含任何输入输出操作。

样例

考虑 $N=5$, $K=2$, $S=[1,3,5,7,9]$, $E=[4,6,8,10,12]$, $W=[1,2,5,2,1]$ 的情况。

评测程序将调用如下函数：

min_charge(2, [1,3,5,7,9], [4,6,8,10,12], [1,2,5,2,1]);

根据上文的示例解释，min_charge 函数应返回 $3$。

注意，这个示例不满足子任务 $2$ 和 $3$ 的条件。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq K \leq N$
• $1 \leq N \leq 2500$
• $1 \leq s_{i} \leq e_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $1 \leq w_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	10	$N \leq 16$
2	17	$K=1$
3	32	对于所有 $i$，$w_{i}=1$
4	26	$N \leq 250$
5	65	无附加限制

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$ $K$
• 第 $1+i$ $(1 \leq i \leq N)$ 行：$S[i-1]$ $E[i-1]$ $W[i-1]$

示例评测程序按以下格式输出：

• 第 $1$ 行：函数 min_charge 返回的值

示例评测程序可能与实际评测程序不同。