시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB1000.000%

문제

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.

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

입력

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.

출력

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

제한

  • $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.

서브태스크

번호배점제한
18

$t\leq s$

29

$n\le 50$ and $s=0$

318

$s=0$

413

$n\leq 50$

514

$n\leq 350$

615

$\epsilon = 1/10$

723

No further constraints

예제 입력 1

2 3 1000 500
0 0
2 0
3 1

예제 출력 1

1000.0

예제 입력 2

2 3 500 3000
0 0
2 0
3 1

예제 출력 2

3387.277541898787

예제 입력 3

2 3 250 750
0 0
2 0
3 1

예제 출력 3

1000.0

예제 입력 4

2 3 0 500
0 0
2 0
3 1

예제 출력 4

353.5533905932738

예제 입력 5

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

예제 출력 5

50.0

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.