Problem A
Astronom

Die Leidenschaft unseres Astronoms ist die Sternbeobachtung. Insbesondere macht es ihm große Freude, $k$ Sterne gleichzeitig durch sein Teleskop zu betrachten. Der Bau eines Teleskops mit Radius $r$ kostet $t\cdot r$ Kronen. Ein neu gebautes Teleskop wird genau auf den Ursprung $(0,0)$ zeigen. Es an einen anderen Ort zu verschieben kostet ebenfalls Mühe: Die Verschiebung des Teleskops um eine Entfernung von $d$ Einheiten verursacht Kosten von $s\cdot d$ Kronen. Der Astronom kann alle Sterne beobachten, die höchstens $r$ von der Stelle entfernt sind, auf die das Teleskop zeigt.

Wie viel kostet es, ein Teleskop zu bauen und zu bewegen, mit dem $k$ Sterne auf einmal beobachtet werden können?

Alle Koordinaten und Entfernungen sind in der euklidischen Ebene angegeben.

Beispiel

Hier ist ein Beispiel mit $n=3$ Sternen an den Positionen $(0,0)$, $(2,0)$ und $(3,1)$. Der schraffierte Bereich zeigt ein Teleskop mit Radius $1$, das auf $(1,0)$ gerichtet ist und zwei Sterne abdeckt; dieses kostet $s + t$ Kronen und ist eine optimale Lösung für die Beispieleingabe  $3$. Das Bild zeigt auch optimale Lösungen für die Beispieleingaben $1$, $2$, und $4$.

Eingabe

Die erste Zeile besteht aus vier ganzen Zahlen: die Anzahl $k$ der Sterne, die der Astronom beobachten will, die Anzahl $n$ der Sterne am heutigen Himmel, die Verschiebungskosten $s$, und die Kosten für den Bau des Teleskops $t$. Dann folgen $n$ Zeilen, wobei die $i$-te Zeile die ganzzahligen Koordinaten $x_ i$ und $y_ i$ des $i$-ten Sterns enthält.

Ausgabe

Eine einzige reelle Zahl: die Mindestanzahl von Kronen, die der Astronom ausgeben muss.

Beschränkungen und Bewertung

Du kannst davon ausgehen, dass

1. $1\leq k\leq n\leq 700$.

2. $x_ i, y_ i\in \{ -10^9,\ldots , 10^9\} $ für alle $i\in \{ 1,\ldots ,n\} $.

3. $s,t\in \{ 0,\ldots , 10^9\} $.

4. Deine Ausgabe wird akzeptiert, wenn sie innerhalb einer relativen oder absoluten Toleranz von $\epsilon = 10^{-6}$ der richtigen Antwort liegt.

Deine Lösung wird mit einer Reihe von Testgruppen getestet, von denen jede eine bestimmte Anzahl von Punkten wert ist. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine Testgruppe zu erhalten, musst du alle Testfälle in der Testgruppe lösen. Deine endgültige Punktzahl ist die maximale Punktzahl für eine einzelne Einsendung.

2 3 1000 500
0 0
2 0
3 1

1000.0

2 3 500 3000
0 0
2 0
3 1

3387.277541898787

2 3 250 750
0 0
2 0
3 1

1000.0

2 3 0 500
0 0
2 0
3 1

353.5533905932738

3 4 0 10
0 0
10 0
5 10
5 5

50.0