Timpani Retuning

A timpano is a large drum that is tuned to one pitch and sounds only that pitch. A player uses $D$ timpani, numbered 1, 2, ..., $D$ from the lowest one up.

The piece to be played has $N$ notes. Note $i$ sounds $T_i$ seconds into the piece and has pitch $P_i$. Every note of the piece lies inside a single octave, from F up to E, and those twelve pitches are numbered 1 through 12 from the lowest one up.

A timpano can be tuned only to one of these twelve pitches. A drum sounds only the pitch it is tuned to at that moment, so note $i$ can be played if and only if one of the drums is tuned to $P_i$ at time $T_i$.

Before the piece starts, the player tunes each drum to any pitch, and that costs no time. During the piece the player has to retune drums to reach the required pitches on time. The rules for retuning are these.

• At every moment, drum $i+1$ must be tuned higher than drum $i$. While one drum is retuned its pitch passes through the pitches between the old one and the new one, so this order must hold throughout the retuning.
• One retuning covers one drum and takes one uninterrupted interval of time. During that interval no note sounds and no other drum is retuned.
• So if $k$ retunings happen between note $i$ and note $i+1$, those $k$ intervals must fit without overlapping inside an interval of length $T_{i+1} - T_i$.

Retuning is hard work, so the player wants as much time as possible for it. Find the time of the shortest retuning in the piece when that time is made as large as possible.

The first line contains the number of notes $N$ and the number of drums $D$. ($1 \le N \le 100$, $1 \le D \le 4$)

Each of the next $N$ lines contains the time $T_i$ and the pitch $P_i$ of note $i$. ($0 \le T_1 < T_2 < \cdots < T_N \le 10^9$, $1 \le P_i \le 12$)

All input values are integers.

Print on one line the largest time in seconds that the shortest retuning can get. Round the value at the third decimal place and always print two digits after the decimal point. If the whole piece can be played without a single retuning, print 0.00.

The exact answer is a reduced fraction whose denominator is at most $D$, so the rounding is never ambiguous.