Problem A
Astronoms

Astronoms aizraujas ar zvaigžņu vērošanu. Konkrētāk, viņš izjūt neaprakstāmu prieku vienlaikus vērojot $k$ zvaigznes caur savu teleskopu. Teleskopa ar rādiusu $r$ izgatavošana maksā $t\cdot r$ kronas. Jauns teleskops būs vērsts tieši uz sākumpunktu $(0,0)$. Tā pavēršana uz citu punktu debesīs rada papildus izmaksas; pavēršot teleskopu uz citu punktu debesīs attālumā $d$ vienības izmaksā $s\cdot d$ kronas. Astronoms var novērot visas zvaigznes, kas atrodas attālumā ne vairāk kā $r$ no punkta, uz kuru ir pavērsts teleskops.

Cik maksās izveidot un pavērst teleskopu, lai varētu novērot $k$ zvaigznes vienlaikus?

Visas koordinātas un attālumi ir doti Eiklīda plaknē.

Piemērs

Lūk, piemērs ar $n=3$ zvaigznēm, kuru koordinātas ir $(0,0)$, $(2,0)$ un $(3,1)$. Iekrāsotais laukums reprezentē teleskopu ar rādiusu $1$, kas ir pavērsts uz koordinātām $(1,0)$ un tajā vērojamas divas zvaigznes. Tas izmaksā $s+t$ kronas un ir optimāls risinājums $3$. parauga ievaddatiem. Attēls arī parāda optimālos risinājumus $1$., $2$. un $4$. parauga ievaddatiem.

Ievaddati

Pirmā rindiņa satur četrus veselus skaitļus: zvaigžņu skaitu $k$, ko astronoms vēlas novērot, zvaigžņu skaitu šīs nakts debesīs $n$, teleskopa pārvietošanas izmaksas $s$ un teleskopa izgatavošanas izmaksas $t$. Tad seko $n$ rindas, kur $i$-tajā rindā ir $i$-tās zvaigznes koordinātes $x_i$ un $y_i$.

Izvaddati

Viens reāls skaitlis: vismazākais izdevumu apjoms kronās, kas astronomam jāiztērē.

Ierobežojumi un vērtēšana

Var pieņemt, ka

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

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

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

4. Jūsu atbilde tiks uzskatīta par pareizu, ja tās absolūtā vai relatīvā kļūda ir $ϵ={10}^{-6}$ robežās.

Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām. Katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.

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