Longest k-Fold Overlap Interval Set

You are given a set \(\mathbf{I}\) of \(n\) open intervals on the real line \(\text{L}\) and a positive integer \(k\). Your task is to select a subset \(\mathbf{S} \subseteq \mathbf{I}\) (i.e. choose some intervals in \(\mathbf{I}\)) such that for any point \(x \in \text{L}\), the number of intervals in \(\mathbf{S}\) that cover \(x\) is at most \(k\). Moreover, you wish to maximize the total length of the chosen intervals, i.e., maximize \(\sum_{z\in \mathbf{S}} |z|\), where \(|z|\) denotes the length of the open interval \(z\).

This quantity is called the length of the longest \(k\)-fold overlap interval set of \(\mathbf{I}\). Given \(\mathbf{I}\) and \(k\), compute the maximum total length possible.

Note: Each interval \((l,r)\) is open (i.e. does not include its endpoints) and its length is \(r-l\).

inputFormat

The first line contains two numbers: an integer \(n\) and an integer \(k\) (with \(1 \leq k \leq n\)). Each of the following \(n\) lines contains two real numbers \(l\) and \(r\) (with \(l < r\)) representing an open interval \((l, r)\) on the real line \(\text{L}\).

outputFormat

Output a single real number which is the maximum total length of a \(k\)-fold overlap interval set, printed with at least 6 digits after the decimal point.

sample

3 1
0 3
1 5
4 6

5.000000