计算机科学家很少帮助打击乐手，但今天情况将有所改变。由于我们无法同时帮助所有打击乐手，我们首先关注定音鼓手。从术语上讲，timpani 是 timpano 的复数形式，而演奏 timpani 的人被称为定音鼓手（timpanist）。

定音鼓（timpano）是一种可以调至特定音高的大鼓，定音鼓手使用一组有序的 $D$ 个定音鼓。在这次演奏中，他们要演奏一段包含 $N$ 个音符的乐曲。第 $i$ 个音符出现在乐曲开始后的 $T_i$ 秒，音高为 $P_i$。$P_i$ 是以下十二个音符之一：

{ F, F#, G, G#, A, A#, B, C, C#, D, D#, E }

在任何给定时间，一个定音鼓只能用于演奏它当前调好的音高，因此定音鼓手可以在时间 $T_i$ 演奏音符 $i$，当且仅当其中一个定音鼓在时间 $T_i$ 被调至音高 $P_i$。

乐曲中的每个音符都在一个八度音阶范围内，从 F 到 E，这意味着上述可能的音符列表是按音高升序排列的。为了使计算稍微容易一些，我们使用 1 到 12 的整数来表示这 12 个音调：

（即 F 用 1 表示，F# 用 2 表示，以此类推，E 用 12 表示）。

这些是定音鼓可以调至的唯一音高。

在乐曲开始前，定音鼓手可以自由地将每个定音鼓调至他们想要的任何音高。然而，在乐曲演奏过程中，他们可能需要在音符之间快速重新调音，以便能够在正确的时间演奏所需的音高。鼓的编号为 1 到 $D$。在任何时间点，鼓 $i+1$ 必须保持调至比鼓 $i$ 更高的音高。重新调整单个鼓必须在一段不间断的时间内完成，在此期间不能演奏任何音符，也不能调整其他鼓。因为这不是一个简单的过程，定音鼓手希望尽可能多地给自己留出时间。特别地，他们希望最大化他们在乐曲中必须执行的最快重新调音所拥有的时间。

输入格式

第一行包含两个整数 $N$ 和 $D$，表示要演奏的音符数量和可用的鼓数量（$1 \le N \le 100$；$1 \le D \le 4$）。接下来的 $N$ 行，每行包含两个整数 $T_i$ 和 $P_i$，表示第 $i$ 个音符的时间和音高（$0 \le T_1 < T_2 < \dots < T_{N-1} < T_N \le 10^9$；$1 \le P_i \le 12$，对于 $1 \le i \le N$）。

对于本题 60% 的分数，$N \le 50$ 且 $D \le 3$。

输出格式

输出一行，包含一个实数（保留两位小数），表示定音鼓手在最快重新调音时可以拥有的最大时间（以秒为单位），如果不需要重新调音，则输出 0.00。

样例

样例输入 1

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

样例输出 1

5.00

说明 1

仅使用 1 个鼓时，定音鼓手必须在每个音符后重新调音，以便演奏下一个音符。 使用 2 个鼓时，答案将变为 10.00（通过将较高的鼓保持在音高 12 实现）。

样例输入 2

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

样例输出 2

4.50

说明 2

前 6 个音符仅包含 4 个音高 1, 3, 5 和 6。同样，最后 6 个音符仅包含 1, 3, 6, 8。 唯一的最佳策略是预先将 4 个鼓调至 1, 3, 5 和 6。在第六个音符之后，定音鼓手可以花费 4.5 秒将最高的鼓重新调至 8，然后再花费 4.5 秒将第二高的鼓重新调至 6，刚好在演奏第七个音符之前完成。

样例输入 3

2 4
40287 8
20338194 8

样例输出 3

0.00

说明 3

这是一个更典型的定音鼓部分，仅涉及一个音符，因此无需重新调音。