Description

Given a set $\mathbf{I}$ of $n$ open intervals on the real line $\text{L}$ and a positive integer $k$, design an algorithm to select a set of open intervals $\mathbf{S} \subseteq \mathbf{I}$ such that at any point $x$ on $\text{L}$, the number of intervals in $\mathbf{S}$ that contain $x$ is at most $k$, and $\sum_{z \in \text{S}} \lvert z \rvert$ is maximized ($\lvert z \rvert$ denotes the length of the open interval $z$).

Such a set $\mathbf{S}$ is called a longest $k$-overlap interval set of $\mathbf{I}$. The value $\sum_{z \in \text{S}} \lvert z \rvert$ is called the length of a longest $k$-overlap interval set.

Given the set of open intervals $\mathbf{I}$ and the positive integer $k$, compute the length of a longest $k$-overlap interval set of $\mathbf{I}$.

Input Format

The first line contains two positive integers $n$ and $k$, denoting the number of open intervals and the allowed maximum number of overlaps. Each of the next $n$ lines contains two integers, the left and right endpoints $l, r$ of an open interval. It is guaranteed that $l < r$.

Output Format

Output the length of a longest $k$-overlap interval set.

4 2
1 7
6 8
7 10
9 13 

15

Hint

For $100\%$ of the testdata, $1 \le n \le 500$, $1 \le k \le 3$, $1 \le l < r \le 10^5$.

Translated by ChatGPT 5