Problem A
Astronomer
Languages
da
de
en
fi
lt
lv
pl
uk
The astronomer has a passion for stargazing. In particular, he gets immense pleasure out of gazing at $k$ stars simultaneously through his telescope. Building a telescope with radius $r$ costs $t\cdot r$ kroner. A newly built telescope will point exactly at the origin $(0,0)$. Moving it to point somewhere else also takes effort; shifting the telescope a distance of $d$ units incurs a cost of $s\cdot d$ kroner. The astronomer can observe all stars at distance at most $r$ from where the telescope points.
How much does it cost to build and move a telescope that allows $k$ stars to be observed at once?
All coordinates and distances are given in the Euclidean plane.
Example
Here is an example with $n=3$ stars at positions $(0,0)$, $(2,0)$, and $(3,1)$. The shaded area shows a telescope of radius $1$ pointing at $(1,0)$ covering two stars; this costs $s + t$ kroner and is an optimal solution to sample input $3$. The image also shows optimal solutions to sample inputs $1$, $2$, and $4$.
Input
The first line consists of four integers: the number $k$ of stars the astronomer wants to observe, the number $n$ of stars in tonight’s sky, the shifting cost $s$, and the telescope building cost $t$. Then follow $n$ lines, where the $i$th line contains the integer coordinates $x_ i$ and $y_ i$ of the $i$th star.
Output
A single real number: the minimum number of kroner that the astronomer needs to spend.
Constraints and Scoring
You can assume

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

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

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

Your output is accepted if it is within a relative or absolute tolerance of $\epsilon = 10^{6}$ of the correct answer.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
Group 
Points 
Constraints 
$1$ 
$8$ 
$t\leq s$ 
$2$ 
$9$ 
$n\le 50$ and $s=0$ 
$3$ 
$18$ 
$s=0$ 
$4$ 
$13$ 
$n\leq 50$ 
$5$ 
$14$ 
$n\leq 350$ 
$6$ 
$15$ 
$\epsilon = 1/10$ 
$7$ 
$23$ 
No further constraints 
Sample Input 1  Sample Output 1 

2 3 1000 500 0 0 2 0 3 1 
1000.0 
Sample Input 2  Sample Output 2 

2 3 500 3000 0 0 2 0 3 1 
3387.277541898787 
Sample Input 3  Sample Output 3 

2 3 250 750 0 0 2 0 3 1 
1000.0 
Sample Input 4  Sample Output 4 

2 3 0 500 0 0 2 0 3 1 
353.5533905932738 
Sample Input 5  Sample Output 5 

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