Problem A
Astronomer

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. $1\leq k\leq n\leq 700$.

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

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

4. 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.

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