Problem A
Astronom

Pasją pewnego astronoma jest obserwacja gwiazd. W szczególności czerpie on ogromną przyjemność z wpatrywania się w $k$ gwiazd jednocześnie przez swój teleskop. Budowa teleskopu o promieniu $r$ kosztuje $t\cdot r$ koron. Nowo zbudowany teleskop będzie wskazywał dokładnie na początek $(0,0)$. Przesuwanie go tak, by wskazywał gdzie indziej, również wymaga wysiłku; przesunięcie teleskopu o odległość $d$ jednostek kosztuje $s\cdot d$ koron. Astronom może obserwować wszystkie gwiazdy w odległości co najwyżej $r$ od miejsca, na które wskazuje teleskop.

Ile kosztuje zbudowanie i przesunięcie teleskopu, który umożliwia jednoczesną obserwację $k$ gwiazd?

Wszystkie współrzędne i odległości podane są w płaszczyźnie euklidesowej.

Przykład

Oto przykład z $n=3$ gwiazdami na pozycjach $(0,0)$, $(2,0)$ oraz $(3,1)$. Zacieniowany obszar pokazuje teleskop o promieniu $1$ skierowany na $(1,0)$ obejmujący dwie gwiazdy; kosztuje to $s+t$ koron i jest optymalnym rozwiązaniem dla przykładowego wejścia $3$. Obraz pokazuje również optymalne rozwiązania dla przykładowych wejść $1$, $2$ oraz $4$.

Wejście

Pierwszy wiersz składa się z czterech liczb całkowitych: liczba $k$ gwiazd, które astronom chce obserwować, liczba $n$ gwiazd na dzisiejszym niebie, koszt przesunięcia $s$, oraz koszt budowy teleskopu $t$. Następnie znajduje się $n$ wierszy, gdzie $i$-ty wiersz zawiera współrzędne całkowite $x_i$ oraz $y_i$ gwiazdy o numerze $i$.

Wyjście

Pojedyncza liczba rzeczywista: minimalna liczba koron, którą astronom musi wydać.

Ograniczenia i punktacja

Możesz założyć

1. $1\le k\le n\le 700$.

2. $x_i,y_i\in \{-{10}^9,\dots ,{10}^9\}$ dla każdego $i\in \{1,\dots ,n\}$.

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

4. Twoja odpowiedź będzie zaakceptowana, jeśli mieści się w względnej lub bezwzględnej tolerancji $ϵ={10}^{-6}$ od prawidłowej odpowiedzi.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

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