United States of Eurasia

In the year 5013 an emperor conquered the continent of Eurasia and founded the United States of Eurasia. The country is wide enough to cover the whole continent and its population is large, so the emperor wants to split the territory into provinces and manage them efficiently. The country has $N$ houses, and house $i$ stands at $(x_i, y_i)$ in the two dimensional Euclidean plane. The emperor assigns the houses to provinces under the following conditions.

• Condition 1. Each province manages the houses whose $x$ coordinate falls inside one interval. A province may manage every house, and a province may manage no house at all.
• Condition 2. Every house must be managed by exactly one province.
• Condition 3. At most $K$ provinces can be created.

Eurasia has many races, religions and peoples. To prevent conflicts among them, the division inside each province has to be as small as possible. The division of a province is the distance between the farthest pair of houses that the province manages. The distance is the Euclidean distance. Help the emperor and make the largest division among the provinces as small as possible.

The first line contains the number of houses $N$ and the number of provinces $K$, separated by a space.

Each of the next $N$ lines contains two integers $x_i$ and $y_i$ separated by a space, which means that a house stands at $(x_i, y_i)$.

Let $M$ be the largest division among the provinces when the houses are split so that this largest division is as small as possible. Print $M^2$. All coordinates are integers, so $M^2$ is always an integer.

• $1 \le K \le N \le 250\,000$
• All house coordinates are distinct. That is, if $i \ne j$, then $x_i \ne x_j$ or $y_i \ne y_j$ holds.
• $0 \le x_i, y_i \le 10^9$