题目描述

本题译自 CCO 2015 Day2 T2「Tiampist」

计算机科学家不常帮助打击乐家，但今天，这将改变。既然我们没法同时帮助所有打击乐家，那么就先设法帮助定音鼓手。

定音鼓是一种能被调整至特定音调的大鼓。定音鼓手用编号为 $1\dots D$ 的 $D$ 个定音鼓演奏。现在，他们在演奏一个有 $N$ 个音符的小节，第 $i$ 个音符演奏 $T_i$ 秒，它的音调是 $P_i$，而 $P_i$ 属于 $\{\text{F},$ $\text{F}^♯,$ $\text{G,}$ $\text{G}^♯,$ $\text{A},$ $\text{A}^♯,$ $\text{B},$ $\text{C},$ $\text{C}^♯,$ $\text{D},$ $\text{D}^♯,$ $\text{E}\}$ 这 12 个音符中的一个音符。

在一个时刻，一个定音鼓必须先被调到某个音调，才能用来弹奏这个音调，因此定音鼓手能演奏音符 $i$ 当且仅当这个定音鼓在时间 $T_i$ 调到了音调 $P_i$。

在这个片段当中的每个音符都是在一个八度的范围内，从 $\text{F}$ 上至 $\text{E}$，这就意味着上面可能的音符的音调是升序排序的。为了使你的计算更加方便，我们将使用整数 $1$ 到 $12$ 来表示这十二个音符。

1	2	3	4	5	6	7	8	9	10	11	12
$\text{F}$	$\text{F}^♯$	$\text{G}$	$\text{G}^♯$	$\text{A}$	$\text{A}^♯$	$\text{B}$	$\text{C}$	$\text{C}^♯$	$\text{D}$	$\text{D}^♯$	$\text{E}$

以上是所有定音鼓能调到的音调。

在演奏开始前，定音鼓手可以随意调整各个定音鼓到任意他们想要的音调。然而，在演奏时，他们可能需要在音符间隙快速地调整他们，这样他们才能在正确的时候演奏出正确的音符。这些鼓从 $1$ 到 $D$ 编号，在任意时刻，鼓 $i+1$ 的音调必须比鼓 $i$ 的音调高。鼓手必须在（当前时刻）不需要演奏时才能调整一个鼓的音高，并且鼓手一次只能调整一个鼓的音高（假设没有人帮他调节）。

因此，这并不是一件简单的事，定音鼓手想要让他们有尽可能多的时间调节。具体来说，他们想要最大化在演奏过程中的调整时间以便使他们可以在演奏中以最快速度做必要的音调调节。

输入格式

第一行两个整数 $N,D$，分别表示被弹奏的音符和鼓的数量。

接下来 $N$ 行每行两个整数 $T_i$ 和 $P_i$，表示第 $i$ 个音符演奏的时间和音调。

输出格式

输出一行包含一个实数，下取整至两位小数，表示最大的调整时间。输出 $0.00$ 表示没有必要重新调节。

7 1
100 1
120 3
130 5
140 6
150 8
165 10
170 12

5.00

12 4
0 1
2 1
3 3
6 1
9 6
12 5
21 1
23 1
24 3
27 1
30 8
33 6

4.50

2 4
40287 8
20338194 8

0.00

提示

【样例解释 1】

如果只有一个鼓，定音鼓手为了可以演奏下一个音符，必须在每个音符弹奏后重新调节。

如果有两个鼓，答案应该是 $10.00$，当留下高音鼓调到音调 $12$ 时达到这个答案。

【样例解释 2】

前六个音符里只有四个音调：$1$，$3$，$5$，$6$，类似的，最后六个音符里只有 $1$，$3$，$6$，$8$ 四个音调。

一个最佳策略是，预先调整四个鼓到 $1$，$3$，$5$，$6$，在第六个音符后，定音鼓手可以花 $4.50$ 秒调整最高音的鼓到音调 $8$，然后另外 $4.50$ 秒调整次高音鼓到音调 $6$，完成时刚好是时候去弹奏第七个音符。

【样例解释 3】

则是一个更为典型的定音鼓片段，只包含一个音符，因此不需要重新调节。

【数据范围】

对于 $60\%$ 的数据，$1\le N \le 50,1\le D\le 3$；

对于 $100\%$ 的数据，$1\le N \le 100,$ $1\le D\le 4,$ $0\le T_1<T_2<...<T_{N-1}<T_N\le 10^9,$ $1\le P_i \le 12(1\le i \le N)$。