Problem A
Astronom

Astronomen elsker stjernekiggeri. Han får særlig glæde af at betragte $k$ stjerner samtidigt gennem sit teleskop. At bygge et teleskop med radius $r$ koster $t \cdot r$ kroner. Et nybygget teleskop vil pege præcis på origo $(0,0)$. At få det at pege et andet sted hen kræver også en indsats; at flytte teleskopet en afstand på $d$ enheder koster $s \cdot d$ kroner. Astronomen kan observere alle stjerner med afstand højst $r$ fra, hvor teleskopet peger.

Hvor meget koster det at bygge og flytte et teleskop, der tillader observation af $k$ stjerner på én gang?

Alle koordinater og afstande er angivet i det euklidiske plan.

Eksempel

Her er et eksempel med $n=3$ stjerner på positionerne $(0,0)$, $(2,0)$ og $(3,1)$. Det farvelagte område viser et teleskop med radius $1$, der peger på $(1,0)$ og dækker to stjerner; dette koster $s + t$ kroner og er en optimal løsning på eksempel $3$ forneden. Billedet viser desuden optimale løsninger på eksempler $1$, $2$ og $4$.

Indlæsning

Første linje består af fire heltal: antallet $k$ af stjerner, som astronomen ønsker at observere, antallet $n$ af stjerner på aftenens stjernehimmel, omkostningen $s$ ved at flytte teleskopet og omkostningen $t$ ved at bygge et teleskop. Derefter følger $n$ linjer, hvor den $i$’te linje indeholder de heltallige koordinater $x_ i$ og $y_ i$ for den $i$’te stjerne.

Udskrift

Et enkelt reelt tal: det mindste beløb i kroner, som astronomen skal bruge. Tallet angives i angelsaksisk format, dvs. med decimalpunktum som vist i eksemplerne.

Begrænsninger og pointgivning

Du kan antage at følgende gælder:

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

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

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

4. Dit svar accepteres, hvis det er inden for en relativ eller absolut tolerance på $\epsilon = 10^{-6}$ af det korrekte svar.

Din løsning vil blive testet på en række testgrupper, hver med en vist antal point. Hver testgruppe indeholder en række testfald. For at opnå point for en testgruppe skal du løse alle testfald i testgruppen. Din endelige score vil være den højeste score for en enkelt indsendelse.

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