팀파니 조율

팀파니는 음 하나로 조율해 두고 그 음만 낼 수 있는 큰 북이다. 연주자는 팀파니 $D$대를 낮은 쪽부터 1번, 2번, ..., $D$번으로 놓고 쓴다.

연주할 곡에는 음이 $N$개 있다. $i$번째 음은 곡이 시작하고 $T_i$초 뒤에 울리고, 높이는 $P_i$이다. 이 곡의 음은 모두 F부터 E까지 한 옥타브 안에 들어가고, 그 열두 음에 낮은 쪽부터 1번부터 12번까지 번호를 붙인다.

팀파니를 조율할 수 있는 음도 이 열두 가지뿐이다. 팀파니는 그 순간 조율되어 있는 음만 내므로, $T_i$초에 팀파니 가운데 하나가 $P_i$로 조율되어 있어야 $i$번째 음을 칠 수 있다.

곡이 시작하기 전에는 각 팀파니를 원하는 음으로 마음대로 조율해 둘 수 있고, 여기에는 시간이 들지 않는다. 곡이 흐르는 동안 필요한 음을 제때 내려면 중간에 다시 조율해야 한다. 조율 규칙은 다음과 같다.

• 어느 순간에도 $i+1$번 팀파니는 $i$번 팀파니보다 높은 음이어야 한다. 한 대를 조율하는 동안 그 음은 원래 음과 새 음 사이를 지나가므로, 조율하는 내내 이 순서가 지켜져야 한다.
• 조율 한 번은 팀파니 한 대만 대상으로 하고, 끊기지 않는 시간 구간 하나를 차지한다. 그 구간 안에서는 음을 치지 않고 다른 팀파니도 조율하지 않는다.
• 그래서 $i$번째 음과 $i+1$번째 음 사이에 조율을 $k$번 한다면, 그 $k$개 구간은 길이가 $T_{i+1} - T_i$인 구간 안에 서로 겹치지 않게 들어가야 한다.

조율은 쉬운 일이 아니라서 연주자는 조율마다 시간을 넉넉히 쓰고 싶다. 곡 전체에서 가장 짧은 조율에 쓰는 시간을 최대로 키운다고 할 때, 그 시간을 구하라.

첫째 줄에 연주할 음의 개수 $N$과 팀파니의 대수 $D$가 주어진다. ($1 \le N \le 100$, $1 \le D \le 4$)

다음 $N$개 줄에 $i$번째 음의 시각 $T_i$와 높이 $P_i$가 한 줄에 하나씩 주어진다. ($0 \le T_1 < T_2 < \cdots < T_N \le 10^9$, $1 \le P_i \le 12$)

모든 입력 값은 정수이다.

가장 짧은 조율에 쓸 수 있는 시간의 최댓값을 초 단위로 한 줄에 출력한다. 소수점 아래 둘째 자리에서 반올림하고, 소수점 아래는 항상 두 자리로 적는다. 조율을 한 번도 하지 않고 곡 전체를 연주할 수 있으면 0.00을 출력한다.

답의 정확한 값은 분모가 $D$ 이하인 기약분수이므로, 반올림이 애매해지는 경우는 없다.