There are $K$ meeting rooms. $N$ meetings intend to use these rooms. Each meeting is numbered from 1 to $N$. Meeting $i$ is represented by a start time $s_i$, an end time $e_i$, and a penalty $w_i$.

These meeting rooms operate under a very specific rule. Meeting $i$ and meeting $j$ are called "related meetings" if at least one of the following conditions is satisfied:

1. The two intervals $[s_i, e_i]$ and $[s_j, e_j]$ have a common interval (even if they only overlap at the start and end times), then $i$ and $j$ are related meetings.
2. The two intervals $[s_i, e_i]$ and $[s_j, e_j]$ do not have a common interval, but there exists another meeting $c$ that is related to $i$, and $[s_c, e_c]$ and $[s_j, e_j]$ have a common interval (even if they only overlap at the start and end times), then $i$ and $j$ are related meetings.

Since meetings can be cancelled, the above definition is determined only using the meetings that are not cancelled. In other words, two meetings that were originally related may no longer be related due to the cancellation of some other meetings.

Meetings that are not cancelled must each be assigned to a meeting room. All related meetings must be assigned to different meeting rooms. For example, note that for three meetings $[1, 3], [3, 5], [5, 7]$, even though there is no common interval between $[1, 3]$ and $[5, 7]$, they must be assigned to three different meeting rooms, not two. Since there are only $K$ meeting rooms, some meetings may need to be cancelled. Since cancelling meeting $i$ incurs a penalty $w_i$, we want to choose the meetings to cancel such that the sum of the penalties is minimized.

The following figure shows 5 meetings $[1, 4], [3, 6], [5, 8], [7, 10], [9, 12]$ with penalties of $1, 2, 5, 2, 1$ respectively. Suppose there are 2 meeting rooms. The example on the left shows the case where $[5, 8]$ is cancelled to satisfy the condition, and the penalty in this case is 5. The example on the right shows the case where $[3, 6]$ and $[9, 12]$ are cancelled to satisfy the condition, and the penalty in this case is 3. Considering all cases, the minimum sum of penalties is 3.

Implementation Details

You must implement the following function:

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

• This function is called exactly once.
• $K$ is the number of meeting rooms.
• The lengths of $S, E, W$ are all $N$.
• Meeting $i + 1$ has a start time $S[i]$, an end time $E[i]$, and a penalty $W[i]$ ($0 \le i \le N - 1$).
• Based on the given number of meeting rooms and meeting information, this function should find the case where the sum of penalties of the cancelled meetings is minimized to satisfy the conditions, and return that sum of penalties.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $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$)

Subtasks

1. (10 points)
   • $N \le 16$
2. (17 points)
   • $K = 1$
3. (32 points)
   • $w_i = 1$ for all $i$
4. (26 points)
   • $N \le 250$
5. (65 points)
   • No additional constraints.

Note

The sum of penalties returned by the min_charge function must match the correct answer. Note that the score for each subtask is the minimum of the scores for all data in that subtask.

Examples

Consider the case where $N = 5, K = 2, S = [1, 3, 5, 7, 9], E = [4, 6, 8, 10, 12], W = [1, 2, 5, 2, 1]$. The grader calls the following function:

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

According to the example explanation in the text, the min_charge function should return 3 upon termination. Note that this example does not satisfy the conditions of subtasks 2 and 3.

Sample grader

The sample grader receives input in the following format:

• Line 1: $N \ K$
• Line $1 + i$ ($1 \le i \le N$): $S[i - 1] \ E[i - 1] \ W[i - 1]$

The sample grader outputs in the following format:

• Line 1: The value returned by the function min_charge

Note that the sample grader may differ from the grader used in actual evaluation.