Država

Μια μακρινή χώρα έχει \(Ν\) πόλεις μέσα της. Μόλις έγιναν οι εκλογές σε αυτή τη χώρα, οπότε εξελέγη ο νέος πρωθυπουργός. Επί του παρόντος, δεν υπάρχει ούτε ένας δρόμος σε αυτή τη χώρα, οπότε ο πρωθυπουργός αποφάσισε να εκσυγχρονίσει τη χώρα συνδέοντας ορισμένες πόλεις με αμφίδρομους αυτοκινητόδρομους και σχηματίζοντας νομούς. Δύο πόλεις θα βρίσκονται στον ίδιο νομό, εάν είναι δυνατό να φτάσετε στη μία πόλη από την άλλη χρησιμοποιώντας τους νεόκτιστους δρόμους. Κάθε πόλη θα βρίσκεται ακριβώς σε μία κομητεία. Κάθε περιοχή αποτελείται από μία ή περισσότερες πόλεις.

Οι πόλεις αναπαρίστανται ως σημεία σε ένα δισδιάστατο σύστημα συντεταγμένων. Ο δρόμος μεταξύ δύο πόλεων αναπαρίσταται ως γραμμικό τμήμα που συνδέει δύο σημεία όπου βρίσκονται οι πόλεις. Το μήκος του δρόμου είναι ίσο με το μήκος του τμήματος της γραμμής σε χιλιόμετρα.

Η χώρα αυτή τη στιγμή υποφέρει από ύφεση, οπότε ο πρωθυπουργός αποφάσισε ότι, λόγω έλλειψης προϋπολογισμού, δεν θα κατασκευάσουν δρόμους μεγαλύτερους από ~D~ χιλιόμετρα. Επιπλέον, ο πρωθυπουργός είναι χαρούμενος για τα μικρά πράγματα, επομένως θα είναι χαρούμενος εάν, τουλάχιστον σε μία κομητεία, υπάρχει ένα μη κενό υποσύνολο πόλεων (μπορεί να περιλαμβάνει όλες τις πόλεις του νομού) όπου το συνολικό άθροισμα των κατοίκων είναι διαιρετό από το ~K~. Για παράδειγμα, αν ~K = 4~ και υπάρχει νομός με πόλεις που έχουν ~3,\;5,\;7~ κατοίκους αντίστοιχα, ο πρωθυπουργός θα είναι ευχαριστημένος επειδή το άθροισμα των κατοίκων στις δύο πρώτες πόλεις είναι ίσο με 8.

Βοηθήστε τον πρωθυπουργό να περικόψει το κόστος προσδιορίζοντας το ελάχιστο ~D~ έτσι ώστε ο πρωθυπουργός να μπορεί να φτιάξει δρόμους και να χαίρεται για τα μικρά πράγματα ταυτόχρονα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~ και ~K\;(1 \leq N \leq 50\,000,\;1 \leq K \leq 30)~. Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει τρεις ακέραιους ~x_i,\;y_i,\;k_i\;(0 \leq x_i, y_i, k_i \leq 100\,000\,000)~, που αντιπροσωπεύουν τη συντεταγμένη ~x~ της πόλης, τη συντεταγμένη ~y~ και τον αριθμό των κατοίκων σε αυτήν την πόλη, αντίστοιχα . Δεν θα υπάρχουν δύο πόλεις με τις ίδιες συντεταγμένες στα δεδομένα εισόδου. Επιπλέον, δεν θα υπάρχει ούτε μία πόλη με τον αριθμό των κατοίκων να διαιρείται με το ~K~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το ελάχιστο ~D~ έτσι ώστε να είναι δυνατή η κατασκευή δρόμων με την προϋπόθεση ότι ο πρωθυπουργός είναι ευχαριστημένος. Τυπώστε το ~D~ στρογγυλοποιημένο σε 3 δεκαδικά ψηφία. Τα δεδομένα εισόδου θα είναι τέτοια ώστε να υπάρχει πάντα λύση.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~40~% των πόντων, ο αριθμός των πόλεων ~N~ θα είναι μικρότερος ή ίσος με ~1000~.

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

input

3 3
0 4 4
1 5 1
2 6 1

output

1.141

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

Ο μόνος τρόπος για να μείνει ευχαριστημένος ο πρωθυπουργός είναι αν όλες οι πόλεις βρίσκονται στον ίδιο νομό. Το ελάχιστο ~D~ για το οποίο αυτό είναι δυνατό είναι ~1.414~.

input

6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10

output

5.657

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

Ο πρωθυπουργός θα χαρεί αν οι 5 πρώτες πόλεις βρίσκονται στον ίδιο νομό. Εάν ~D = 5.657~, ο πρωθυπουργός μπορεί να συνδέσει τις πόλεις ~1,\;2,\;3,\;5~ με την πόλη 4. Σε αυτήν την περίπτωση, το άθροισμα των κατοίκων στις πόλεις ~1,\;2,\;3,\;4,\;5~ θα είναι 11, το οποίο διαιρείται με το 11 , άρα θα χαρεί ο πρωθυπουργός.

input

6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3

output

2.000