Problem Description

This problem is translated from CCO 2015 Day2 T2「Tiampist」

Computer scientists rarely assist percussionists, but today, that will change. Since we can't help all percussionists at once, let's start by helping timpanists.

Timpani are large drums that can be tuned to specific pitches. A timpanist uses $D$ timpani numbered $1 \dots D$ to play a piece with $N$ notes. The $i$-th note is played for $T_i$ seconds and has a pitch $P_i$, which belongs to the set $\{\text{F}, \text{F}^♯, \text{G}, \text{G}^♯, \text{A}, \text{A}^♯, \text{B}, \text{C}, \text{C}^♯, \text{D}, \text{D}^♯, \text{E}\}$.

At any given time, a timpani must be tuned to a specific pitch before it can be used to play that pitch. Therefore, a timpanist can play note $i$ if and only if the timpani is tuned to pitch $P_i$ at time $T_i$.

Each note in this piece is within an octave, ranging from $\text{F}$ to $\text{E}$, meaning the possible pitches are in ascending order. For convenience, we will use integers $1$ to $12$ to represent these twelve pitches.

These are all the pitches to which the timpani can be tuned.

Before the performance, the timpanist can tune each timpani to any pitch they desire. However, during the performance, they may need to quickly adjust them during gaps between notes to play the correct pitch at the right time. The drums are numbered from $1$ to $D$, and at any moment, the pitch of drum $i+1$ must be higher than that of drum $i$. The timpanist can only adjust the pitch of a drum when it is not being played, and they can only adjust one drum at a time (assuming no one else helps).

This is not a simple task, and the timpanist wants to have as much time as possible for adjustments. Specifically, they want to maximize the adjustment time during the performance to make necessary pitch adjustments as quickly as possible.

Input Format

The first line contains two integers $N$ and $D$, representing the number of notes and the number of drums, respectively.

The next $N$ lines each contain two integers $T_i$ and $P_i$, representing the time and pitch of the $i$-th note.

Output Format

Output a single line containing a real number, rounded down to two decimal places, representing the maximum adjustment time. Output $0.00$ if no re-tuning is necessary.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5.00

Sample Input #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

Sample Output #2

4.50

Sample Input #3

2 4
40287 8
20338194 8

Sample Output #3

0.00

Notes/Hints

Sample Explanation 1

If there is only one drum, the timpanist must retune after each note to play the next one.

If there are two drums, the answer should be $10.00$, achieved by leaving the highest drum tuned to pitch $12$.

Sample Explanation 2

The first six notes only have four pitches: $1$, $3$, $5$, $6$, and similarly, the last six notes have four pitches: $1$, $3$, $6$, $8$.

An optimal strategy is to initially tune the four drums to $1$, $3$, $5$, $6$, and after the sixth note, the timpanist can spend $4.50$ seconds tuning the highest drum to pitch $8$, and another $4.50$ seconds tuning the second-highest drum to pitch $6$, just in time to play the seventh note.

Sample Explanation 3

This is a more typical timpani piece, containing only one note, so no retuning is necessary.

Data Range

For $60\%$ of the data, $1 \le N \le 50, 1 \le D \le 3$;

For $100\%$ of the data, $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)$.

见题面 Input 部分

见题面 Output 部分