CF607E.Cross Sum

Genos has been given n distinct lines on the Cartesian plane. Let be a list of intersection points of these lines. A single point might appear multiple times in this list if it is the intersection of multiple pairs of lines. The order of the list does not matter.

Given a query point (p, q), let be the corresponding list of distances of all points in to the query point. Distance here refers to euclidean distance. As a refresher, the euclidean distance between two points (_x_1, _y_1) and (_x_2, _y_2) is .

Genos is given a point (p, q) and a positive integer m. He is asked to find the sum of the m smallest elements in . Duplicate elements in are treated as separate elements. Genos is intimidated by Div1 E problems so he asked for your help.

Genos 在笛卡尔平面上得到了 $n$ 条互不相同的直线。令 表示这些直线所有交点构成的列表。若某一点是多对直线的交点，则该点可能在该列表中重复出现多次。列表中元素的顺序无关紧要。

给定一个查询点 $(p,\,q)$，令 表示 中所有点到查询点 $(p,\,q)$ 的欧几里得距离所构成的列表。其中，两点 $(x_1,\,y_1)$ 与 $(x_2,\,y_2)$ 之间的欧几里得距离为 。

Genos 被给定一个点 $(p,\,q)$ 和一个正整数 $m$。他需要求出 中最小的 $m$ 个元素之和。注意： 中的重复元素被视为不同的元素。由于被 Div1 E 难题吓到了，Genos 向你求助。

The first line of the input contains a single integer n (2 ≤ n ≤ 50 000) — the number of lines.

The second line contains three integers x, y and m (|x|, |y| ≤ 1 000 000, ) — the encoded coordinates of the query point and the integer m from the statement above. The query point (p, q) is obtained as . In other words, divide x and y by 1000 to get the actual query point. denotes the length of the list and it is guaranteed that .

Each of the next n lines contains two integers a__i and b__i (|a__i|, |b__i| ≤ 1 000 000) — the parameters for a line of the form: . It is guaranteed that no two lines are the same, that is (a__i, b__i) ≠ (a__j, b__j) if i ≠ j.

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 50,000 $）—— 表示直线的数量。

第二行包含三个整数 $ x $、$ y $ 和 $ m $（$ |x|, |y| \leq 1,000,000 $，）—— 分别为查询点的编码坐标以及上述题干中提到的整数 $ m $。查询点 $ (p,, q) $ 由公式 得到。换言之，将 $ x $ 和 $ y $ 同时除以 $ 1000 $ 即可获得实际的查询点坐标。 表示列表 的长度，且保证 。

接下来的 $ n $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ |a_i|, |b_i| \leq 1,000,000 $）—— 表示形如 的直线的参数。保证任意两条直线互不相同，即当 $ i \neq j $ 时，恒有 $ (a_i,, b_i) \neq (a_j,, b_j) $。

Print a single real number, the sum of m smallest elements of . Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

To clarify, let's assume that your answer is a and the answer of the jury is b. The checker program will consider your answer correct if .

输出一个实数，即数组 中最小的 $m$ 个元素之和。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

具体而言，假设你的答案为 $a$，评测组的标准答案为 $b$。当且仅当 时，评测程序将判定你的答案正确。

In the first sample, the three closest points have distances and .

In the second sample, the two lines y = 1000_x_ - 1000 and intersect at (2000000, 1999999000). This point has a distance of from ( - 1000,  - 1000).

In the third sample, the three lines all intersect at the point (1, 1). This intersection point is present three times in since it is the intersection of three pairs of lines. Since the distance between the intersection point and the query point is 2, the answer is three times that or 6.

在第一个样例中，三个最近的点到查询点的距离分别为 和 。

在第二个样例中，两条直线 $y = 1000x - 1000$ 与 相交于点 $(2000000,\, 1999999000)$。该点到查询点 $(-1000,\, -1000)$ 的距离为 。

在第三个样例中，三条直线均相交于点 $(1,\, 1)$。该交点在 中出现了三次（因为它是三对直线的交点）。由于该交点到查询点的距离为 $2$，因此答案为 $3 \times 2 = 6$。