P11980 [KTSC 2021] 会议室 / meeting
题目背景
本题翻译自 [2021년도 국제정보올림피아드 대표학생 선발고사](https://www.ioikorea.or.kr/archives/ioitst/2021/) 2차 선발고사 [#2 회의실](https://assets.ioikorea.or.kr/ioitst/2021/2/meeting/meeting_statement.pdf)。
**请注意，你不需要也不应该实现 `main` 函数。具体实现方式见【实现细节】部分。**
提交时，请在程序开头添加如下内容，并且无需引用 `meeting.h`：
```cpp
#include
long long min_charge(int K, std::vector S, std::vector E, std::vector W);
```
题目描述
有 $K$ 个会议室。$N$ 个会议需要使用这些会议室。每个会议被赋予从 $1$ 到 $N$ 的编号。会议 $i$ 用开始时间 $s_i$、结束时间 $e_i$ 和违约金 $w_i$ 表示。
这些会议室按照非常特殊的规则运营。会议 $i$ 和会议 $j$ 如果满足以下至少一个条件，则称为相关会议：
1. 两个区间 $[s_i, e_i]$ 和 $[s_j, e_j]$ 有公共部分时（包括仅起点或终点接触的情况），$i$ 和 $j$ 是相关会议。
2. 两个区间 $[s_i, e_i]$ 和 $[s_j, e_j]$ 没有公共部分，但存在另一个会议 $c$ 与 $i$ 相关，且 $[s_c, e_c]$ 和 $[s_j, e_j]$ 有公共部分时（包括仅起点或终点接触的情况），$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$。
### 实现细节
需实现以下函数：
```cpp
long long int min_charge(int K, vector S, vector E, vector W)
```
- 此函数仅被调用一次。
- $K$ 为会议室数量。
- $S, E, W$ 的长度均为 $N$。
- 会议 $i + 1$ 的开始时间为 $S[i]$，结束时间为 $E[i]$，违约金为 $W[i]$（$0 \leq i \leq N - 1$）。
- 此函数需根据会议室数量和会议信息，找到满足条件的最小违约金总和并返回。
提交的源代码中不得调用任何输入输出函数。
输入格式
示例评测程序输入格式：
- 第 $1$ 行: $N \ K$
- 第 $1 + i$ 行（$1 \leq i \leq N$）：$S[i - 1] \ E[i - 1] \ W[i - 1]$
输出格式
示例评测程序输出格式：
- 第 $1$ 行：`min_charge` 函数返回值
实际评测程序可能与示例评测程序不同。
说明/提示
### 约束条件
- $1 \leq K \leq N$
- $1 \leq N \leq 2\,500$
- $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$ 分）
- 无额外约束。
### 评分标准
`min_charge` 函数返回的违约金总和必须与正确答案一致。
各子任务得分为该子任务所有测试数据得分的最小值。
### 示例
- $N = 5$，$K = 2$，$S = [1, 3, 5, 7, 9]$，$E = [4, 6, 8, 10, 12]$，$W = [1, 2, 5, 2, 1]$ 时，评测程序调用：
```cpp
min_charge(2, [1, 3, 5, 7, 9], [4, 6, 8, 10, 12], [1, 2, 5, 2, 1])
```
根据题目描述中的示例，函数应返回 $3$。
请注意此示例不满足子任务 $2$ 和 $3$ 的约束条件。