Minimize Weighted Sum of Circle Radius and Center Distance

Given n integer points on the plane, a positive integer k, and two nonnegative integers s and t, choose a circle that covers at least k of these points. Let the circle's radius be r and the distance from its center to the origin (i.e., (0,0)) be d. The distance is measured as the Euclidean distance. Your task is to determine the minimum value of

$$tr + sd$$

among all circles that cover at least k points.

inputFormat

The first line contains four integers: n, k, s, and t (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ n, 0 ≤ s, t ≤ 10⁹).

The following n lines each contain two integers x and y (|x|, |y| ≤ 10⁹), representing the coordinates of a point.

outputFormat

Output a single value: the minimum value of tr + sd. It is guaranteed that a valid circle exists.

sample

3 2 1 1
0 0
1 1
2 2

1.000000