Problem A
Astronomas

Astronomo aistra – stebėti žvaigždes. Jis patiria neapsakomą malonumą pro teleskopą stebėdamas $k$ žvaigždžių vienu metu. Sukonstruoti teleskopą, kurio spindulys lygus $r$, kainuoja $t\cdot r$ kronų. Naujai sukonstruotas teleskopas nukreipiamas tiesiai į koordinačių pradžios tašką $(0,0)$. Teleskopo nukreipimas į kitą tašką kainuoja. Konkrečiau, nukreipti į tašką, esantį atstumu $d$ nuo pradžios taško, kainuoja $s\cdot d$ kronų. Astronomas gali stebėti visas žvaigždes, nutolusias daugiausiai atstumu $r$ nuo taško, į kurį nukreiptas teleskopas.

Kiek kainuoja sukonstruoti teleskopą ir nukreipti jį į tokį tašką, kad vienu metu būtų galima stebėti $k$ žvaigždžių?

Visos koordinatės ir atstumai skaičiuojami Euklidinėje plokštumoje.

Pavyzdys

Duotos $n=3$ žvaigždės, kurių koordinatės yra $(0,0)$, $(2,0)$ ir $(3,1)$. Tamsesnis plotas žymi teleskopą, kurio spindulys lygus $1$ ir kuris nukreiptas į tašką $(1,0)$. Šis teleskopo aprėpiamas plotas apima dvi žvaigždes. Tai kainuotų $s+t$ kronų ir tai yra optimalus sprendinys $3$-iajam pavyzdžiui. Paveikslėlyje taip pat parodyti optimalūs sprendiniai pavyzdžiams $1$, $2$ ir $4$.

Pradiniai duomenys

Pirmoje eilutėje pateikti keturi sveikieji skaičiai: žvaigždžių, kurias astronomas nori stebėti, skaičius $k$, šiąnakt danguje esančių žvaigždžių skaičius $n$, teleskopo nukreipimo kaina $s$ ir teleskopo konstravimo kaina $t$. Toliau pateikta $n$ eilučių: $i$-ojoje eilutėje pateikiami du sveikieji skaičiai $x_i$ ir $y_i$ – $i$-osios žvaigždės koordinatės.

Rezultatas

Išveskite vieną realųjį skaičių: mažiausią kronų sumą, kurią teks astronomui išleisti.

Ribojimai ir vertinimas

Visada galios šie ribojimai:

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

2. $x_i,y_i\in \{-{10}^9,\dots ,{10}^9\}$ kiekvienam $i\in \{1,\dots ,n\}$.

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

4. Išvestis laikoma teisinga, jeigu jos ir teisingo atsakymo santykinė arba absoliutinė paklaida yra ne didesnė nei $ϵ={10}^{-6}$.

Sprendimas bus testuojamas su keliomis testų grupėmis, kurių kiekviena verta tam tikro skaičiaus taškų. Kiekviena testų grupė sudaryta iš įvairių testų. Testų grupės taškai skiriami tik išsprendus visus grupės testus. Galutinis taškų skaičius lygus daugiausiai surinkusio sprendimo taškų skaičiui.

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