Description

This problem is translated from CCO 2015 Day2 T2 "Tiampist".

Computer scientists do not often help percussionists, but today that will change. Since we cannot help all percussionists at once, let us help the timpanist first.

A timpani is a large drum that can be tuned to a specific pitch. A timpanist performs using $D$ timpani numbered $1 \dots D$. Now they are playing a measure with $N$ notes. The $i$-th note is played at time $T_i$ seconds, and its pitch is $P_i$, where $P_i$ is one of the following 12 notes: $\{\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 moment, a timpani must be tuned to a pitch before it can be used to play that pitch. Therefore, the timpanist can play note $i$ if and only if, at time $T_i$, some timpani is tuned to pitch $P_i$.

All notes in this excerpt are within one octave, from $\text{F}$ up to $\text{E}$, which means the possible pitches above are in increasing order. To make computation easier, we will use integers $1$ to $12$ to represent these twelve notes.

These are all the pitches that each timpani can be tuned to.

Before the performance starts, the timpanist may freely tune each timpani to any pitch they want. However, during the performance, they may need to quickly retune them in the gaps between notes, so that they can play the correct note at the correct time. The drums are numbered from $1$ to $D$. At any time, the pitch of drum $i+1$ must be higher than the pitch of drum $i$. The timpanist may retune a drum only when they are not required to play at that moment, and they can retune only one drum at a time (assume no one helps them tune).

Therefore, this is not easy. The timpanist wants to have as much time as possible for retuning. More specifically, they want to maximize the retuning time during the performance so that they can make necessary pitch changes as quickly as possible while playing.

Input Format

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

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 one real number, floored to two decimal places, representing the maximum retuning time. Output $0.00$ if no retuning is necessary.

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

Hint

[Sample Explanation 1]

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

If there are two drums, the answer should be $10.00$, achieved when the higher-pitched drum is left tuned to pitch $12$.

[Sample Explanation 2]

Among the first six notes, there are only four pitches: $1$, $3$, $5$, $6$. Similarly, among the last six notes, there are only four pitches: $1$, $3$, $6$, $8$.

One optimal strategy is to pre-tune four drums to $1$, $3$, $5$, $6$. After the sixth note, the timpanist can spend $4.50$ seconds tuning the highest-pitched drum to pitch $8$, then another $4.50$ seconds tuning the second-highest drum to pitch $6$, finishing exactly in time to play the seventh note.

[Sample Explanation 3]

This is a more typical timpani excerpt: it contains only one note, so no retuning is needed.

Constraints

For $60\%$ of the testdata, $1\le N \le 50, 1\le D\le 3$.

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

Translated by ChatGPT 5