Timpanist

Οι επιστήμονες υπολογιστών δεν βοηθούν συχνά τους μουσικούς που παίζουν κρουστά, αλλά σήμερα, αυτό θα αλλάξει. Αφού δεν μπορούμε βοηθήσουμε όλους τους μουσικούς που παίζουν κρουστά ταυτόχρονα, εστιάζουμε πρώτα στους τυμπανιστές. Ως ορολογία, το timpani είναι ο πληθυντικός του timpano και ο παίκτης του timpani είναι τιμπανίστας.

Το timpano είναι ένα μεγάλο τύμπανο που μπορεί να συντονιστεί σε ένα συγκεκριμένο βήμα και ένας τιμπανίστας χρησιμοποιεί ένα διατεταγμένο σετ από ~D~ timpani. Σε αυτήν την περίπτωση, παίζουν ένα κομμάτι που έχει ~N~ νότες. Σημειώστε ότι το ~i~ εμφανίζεται ~T_i~ δευτερόλεπτα στο κομμάτι, και έχει τόνο ~P_i~. Το ~P_i~ είναι μία από τις ακόλουθες δώδεκα νότες:

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

Σε μια δεδομένη στιγμή, ένα timpano μπορεί να χρησιμοποιηθεί μόνο για να παίξει τον τόνο στον οποίο είναι συντονισμένο εκείνη τη στιγμή, και επομένως ο τιμπανίστας μπορεί να παίξει μια νότα ~i~ εάν και μόνο εάν ένα από τα timpani είναι συντονισμένο για να παίξει ~P_i~ τη στιγμή ~T_i~.

Κάθε νότα σε αυτό το κομμάτι είναι στο εύρος μιας οκτάβας, από το ~F~ έως το ~E~, που σημαίνει ότι η παραπάνω λίστα με τις πιθανές νότες είναι σε αύξουσα σειρά τόνου. Για να κάνετε τον υπολογισμό σας ελαφρώς πιο εύκολο, θα χρησιμοποιήσουμε ακέραιους αριθμούς από το ~1~ έως το ~12~ για να υποδείξουμε αυτούς τους ~12~ τόνους:

(δηλαδή, το F θα αντιπροσωπεύεται από το ~1~, το F# από το ~2~, ..., το E από το ~12~).

Αυτοί είναι οι μόνοι τόνοι στους οποίους μπορούν να συντονιστούν τα timpani.

Πριν ξεκινήσει το κομμάτι, ο τυμπανίστας μπορεί ελεύθερα να συντονίσει κάθε timpano σε όποιο τόνο θέλει. Ωστόσο, κατά τη διάρκεια του κομματιού, μπορεί να χρειαστεί να τα επανασυντονίσουν γρήγορα ανάμεσα στις νότες για να μπορέσουν να παίξουν τους απαιτούμενους τόνους στη σωστή στιγμή. Τα τύμπανα αριθμούνται από το ~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 < ... < 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~.

Έξοδος

Η έξοδος είναι μία γραμμή που περιέχει έναν πραγματικό αριθμό (στρογγυλοποιημένο σε ~2~ δεκαδικά ψηφία), ο οποίος είναι ο μέγιστος χρόνος (σε δευτερόλεπτα) που μπορεί να έχει ο τυμπανιστής για τον γρηγορότερό του επανασυντονισμό ή ~0.00~ αν δεν χρειάζεται κανένας επανασυντονισμός.

Παραδείγματα

input

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

output

5.00

Επεξήγηση του πρώτου παραδείγματος

Με μόλις ~1~ τύμπανο, ο τυμπανιστής πρέπει να το επανασυντονίζει μετά από κάθε νότα για να παίξει το παραπάνω κομμάτι.

Με ~2~ τύμπανα, η απάντηση θα ήταν ~10.00~ (που επιτυγχάνεται αφήνοντας το μεγαλύτερο τύμπανο συντονισμένο στον τόνο ~12~)

input

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

output

4.50

Επεξήγηση του δεύτερου παραδείγματος

Οι πρώτες ~6~ νότες περιλαμβάνουν μόνο τους ~4~ τόνους ~1, 3, 5~ και ~6~. Παρομοίως, οι τελευταίες ~6~ περιλαμβάνουν μόνο τους ~1, 3, 6, 8~.

Η μοναδική βέλτιστη στρατηγική περιλαμβάνει να προ-συντονίσουμε τα ~4~ τύμπανα στους τόνους ~1, 3, 5~ και ~6~. Μετά από την έκτη νότα, ο τυμπανιστής μπορεί να κάνει ~4.5~ δευτερόλεπτα για να συντονίσει το υψηλότερο τύμπανο στο ~8~ και μετά άλλα ~4.5~ δευτερόλεπτα για να συντονίσει το δεύτερο υψηλότερο τύμπανο στο ~6~, τελειώνοντας πάνω στην ώρα για να παίξει την έβδομη νότα.

input

2 4
40287 8
20338194 8

output

0.00

Επεξήγηση του τρίτου παραδείγματος

Αυτό είναι ένα πιο τυπικό κομμάτι, που περιλαμβάνει μόνο μία νότα και οπότε δεν χρειάζεται επανασυντονισμό.