有 $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 \le i \le N - 1$)。
• 该函数应根据给定的会议室数量和会议信息，找出为了满足条件而需要取消的会议中，违约金总和最小的情况，并返回该违约金总和。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $1 \le K \le N$
• $1 \le N \le 2\,500$
• $1 \le s_i \le e_i \le 10^9$ ($1 \le i \le N$)
• $1 \le w_i \le 10^9$ ($1 \le i \le N$)

子任务

1. (10分) $N \le 16$
2. (17分) $K = 1$
3. (32分) 对于所有 $i$，$w_i = 1$
4. (26分) $N \le 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]$ 的情况。

输入格式 1

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

输出格式 1

3

说明

评测程序调用以下函数： min_charge(2, [1, 3, 5, 7, 9], [4, 6, 8, 10, 12], [1, 2, 5, 2, 1]) 根据正文中的样例说明，min_charge 函数结束时应返回 3。请注意，此样例不满足子任务 2 和 3 的条件。

交互

Sample grader 按以下格式接收输入：

输入格式 1

N K
S[0] E[0] W[0]
...
S[N-1] E[N-1] W[N-1]

输出格式 1

(函数 min_charge 的返回值)

请注意，Sample grader 可能与实际评测中使用的评测程序不同。