题目背景

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 2차 선발고사 #2 회의실。

提交时，请在程序开头添加如下内容，并且无需引用 meeting.h：

#include <vector>

long long min_charge(int K, std::vector<int> S, std::vector<int> E, std::vector<int> 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$。

实现细节

需实现以下函数：

long long int min_charge(int K, vector<int> S, vector<int> E, vector<int> 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 函数返回值

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

5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1

3

5 1
2 6 5
4 6 2
8 8 5
1 3 4
6 8 7

12

提示

约束条件

• $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]$ 时，评测程序调用：

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

  根据题目描述中的示例，函数应返回 $3$。

  请注意此示例不满足子任务 $2$ 和 $3$ 的约束条件。