题目描述

本题译自 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$ 到 $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

数据范围与提示

对于 $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)$。