Witamy na zawodach regionalnych 2022 ICPC(International Collegiate Programming Contest) w Taoyuan!
ICPC to zawody w programowaniu algorytmicznym dla studentów. Ich celem jest pokazanie kreatywności, pracy zespołowej oraz umiejętności pisania kodu, analizowania i rozwiązywania problemów pod presją.
W tym roku zawody regionalne w Taoyuan mają $N$ autorów zadań, ponumerowanych od $1$ do $N$.
Aby poprawić jakość całych zawodów, autorzy zadań odbyli kilka spotkań podczas przygotowań.
Wybór miejsca spotkania jest bardzo ważny, ponieważ trzeba uwzględnić miejsca zamieszkania autorów.
Dla wygody organizator podzielił autorów na $K$ grup. Każda grupa składa się z autorów o kolejnych numerach, a każdy autor należy tylko do jednej grupy.
Autorzy z tej samej grupy mają wspólne miejsce spotkań. Koszt grupy definiujemy jako największą odległość od jej członka do miejsca spotkania.
Znasz położenia $N$ autorów (jako punkty w dwuwymiarowym kartezjańskim układzie współrzędnych) oraz $K$. Czy potrafisz znaleźć minimalną sumę kosztów tych $K$ grup?
Odległość oznacza tutaj odległość euklidesową, czyli dla punktów $(x_1,y_1)$ i $(x_2,y_2)$ wynosi $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.
To zadanie może być nieco trudne. Ponadto niespodziewanie odkrywasz informację, choć nie wiesz, czy jest przydatna. Miejsce zamieszkania każdego autora spełnia pewien wzór. Innymi słowy, $N$ punktów jest generowanych za pomocą następujących wzorów:
$$X_i=(Y_{i-1}\times233811181+1)\bmod(2^{31}-1),\quad\forall i\ge2.$$
$$Y_i=(X_i\times233811181+1)\bmod(2^{31}-1),\quad\forall i\ge1.$$
Powyższe historie są całkowicie fikcyjne, a wszelkie podobieństwa są czysto przypadkowe.
Wejście
Pierwszy wiersz zawiera trzy liczby całkowite $N,K,X_1$, oznaczające odpowiednio liczbę punktów, liczbę przedziałów i ziarno generatora losowego.
Ograniczenia
$1\le K\le N\le2000$.
$1\le X_1\le8831$.
Wyjście
Wypisz jedną liczbę zmiennoprzecinkową oznaczającą minimalną sumę promieni najmniejszych okręgów obejmujących punkty w $K$ segmentach.
Twoja odpowiedź zostanie uznana za poprawną, jeśli błąd bezwzględny lub względny na obu współrzędnych nie przekroczy $10^{-6}$. Formalnie, niech $a$ oznacza twoją odpowiedź, a $b$ odpowiedź jury. Odpowiedź jest poprawna, jeśli $\frac{|a-b|}{\max(1,|b|)}\le10^{-6}$.
Przykład
Wejście 1
100 23 213
Wyjście 1
1319350480.8007326126