P4890 Never·island

You wake up and find yourself in the future, 20,000 years later.

In order to find the legendary Avalon, island has sent out $n$ expedition teams. To keep island stable, island has a gate that leads to the outside world. Each of these $n$ expedition teams needs to go out once for an expedition. The $i$-th expedition team will leave at time $l_i$ and return at time $r_i$. We guarantee that all these values are pairwise distinct. Whenever an expedition team leaves, island’s gate becomes open. However, if this team has obtained a key, then it can decide to close the gate or keep it open. Also, when each expedition team returns, either the gate is already open (since island is known to be the only living area, people inside island will not主动 open the gate for anyone), or the team must have a key to open the gate. Note that upon returning, regardless of whether it has a key, the team can choose to close the gate. For some strange reason, island’s designer made only $k$ keys, which can only be given to $k$ expedition teams. Having a key shows the upper level’s trust in the team, so the team will not give the key to anyone else. To prevent lower-level residents from escaping island, the upper level wants the gate to stay open for as short a time as possible. Please help compute the minimum total time the gate will be open.

The first line contains two positive integers $n, k$. Starting from the second line, there are $n$ lines. Each line contains two numbers describing $l_i, r_i$.

One positive integer, representing the answer.

【Sample Explanation】 ``` ④ ================ ③/⑤ ------- ------ ② ------------------------- ① ========================= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 State X O O O X X X X O X X X X X O O ``` Among them, expedition teams No. 1 and No. 4 will carry keys. 【Constraints】 For $30\%$ of the testdata, $n \leq 20$. For $60\%$ of the testdata, $n \leq 200$. For all testdata, $n \leq 2000$. $1 \leq l_i < r_i \leq 10^9, k \le n$. Translated by ChatGPT 5