Page not loading? Try clicking here.
Placeholder

#8198
Special judge
Subtask

천문학자 (Astronomer) 5s 1024MB

Problems

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.


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 ith line contains the integer coordinates x_i and y_i of the ith star.

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


Output

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


Subtask

# Score Condition
#18

t \le s

#29

n \le 50 , s = 0

#318

s=0

#413

n \le 50

#514

n \le 350

#615

\epsilon = 1/10

#723

No further constraints


Example #1

2 3 1000 500
0 0
2 0
3 1
1000.0

Example #2

2 3 500 3000
0 0
2 0
3 1
3387.277541898787

Example #3

2 3 250 750
0 0
2 0
3 1
1000.0

Example #4

2 3 0 500
0 0
2 0
3 1
353.5533905932738

Example #5

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

Source

BOI 2023

You must sign in to write code.