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.

N/A

N/A

In the first sample, the three closest points have distances  and . In the second sample, the two lines $ y=1000x-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 $ .