Astronomer

문제

The astronomer has a passion for stargazing. In particular, he gets immense pleasure out of gazing at $kk$ stars simultaneously through his telescope. Building a telescope with radius $rr$ costs $t\cdot rt\backslash cdot\; r$ kroner. A newly built telescope will point exactly at the origin $(0,0)(0,0)$. Moving it to point somewhere else also takes effort; shifting the telescope a distance of $dd$ units incurs a cost of $s\cdot ds\backslash cdot\; d$ kroner. The astronomer can observe all stars at distance at most $rr$ from where the telescope points.

How much does it cost to build and move a telescope that allows $kk$ stars to be observed at once?

All coordinates and distances are given in the Euclidean plane.

Here is an example with $n=3n=3$ stars at positions $(0,0)(0,0)$, $(2,0)(2,0)$, and $(3,1)(3,1)$. The shaded area shows a telescope of radius $11$ pointing at $(1,0)(1,0)$ covering two stars; this costs $s+ts\; +\; t$ kroner and is an optimal solution to sample input $33$. The image also shows optimal solutions to sample inputs $11$, $22$, and $44$.

입력

The first line consists of four integers: the number $kk$ of stars the astronomer wants to observe, the number $nn$ of stars in tonight's sky, the shifting cost $ss$, and the telescope building cost $tt$. Then follow $nn$ lines, where the $ii$th line contains the integer coordinates $x_{i}x\_i$ and $y_{i}y\_i$ of the $ii$th star.

출력

A single real number: the minimum number of kroner that the astronomer needs to spend.

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