JOI Country Road Project

JOI Country is represented as a $x\times y$ grid with $n$ towns whose coordinates are given by $(x_i, y_i)$ for $i=1,2,\dots,n$. There are a total of $\frac{n\cdot(n-1)}{2}$ possible roads connecting every distinct pair of towns. For any two towns $a$ and $b$, the cost to build a road between them is

Given an integer $k$, your task is to calculate the total cost of the cheapest $k$ roads among all possible roads. Note that if a road from town $a$ to town $b$ is built, you cannot (and need not) build the road from $b$ to $a$, as they are considered the same.

inputFormat

The first line contains two integers $n$ and $k$, where $n$ is the number of towns and $k$ is the number of cheapest roads to select.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$, representing the coordinates of the $i$-th town.

outputFormat

Output one integer, the total cost needed for the cheapest $k$ roads.

sample

3 2
1 1
2 2
3 3

4