You are given an infinite 2-D grid.

There are: N fixed points on the grid that must be lit. K types of light towers.

Each tower type i has: - A cost per unit distance ki (for each one unit of radius, the cost is ki)

You may place any number of towers of any type at any grid position. You may choose any non-negative radius r for each placed tower.

If you place a tower of type i with radius r, then: - It lights all points within distance r from its position. - Its cost is: r * ki

A fixed point is considered lit if it lies within the radius of at least one placed tower.

Your task is to light all N fixed points with minimum total cost.

Constraints 1 <= N <= 2*10^5,
1 <= K <= 2*10^5,
-1e9 <= xi, yi <= 1e9,
1 <= ki <= 1e9

distance between two point : dist(a, b) = sqrt( (ax — bx)^2 + (ay — by)^2 )