题目描述

In the year 5013, jh05013 conquered the Eurasian Continent and found “jh land”. “jh land” encompasses the whole continent, and jh05013 aims to divide the country into “districts” to govern them efficiently, since it is extremely large and populated. There are $N$ houses in “jh land”, and each house is located at $(x_i, y_i)$ of a 2D Cartesian coordinate system. jh05013 keeps the following conditions when dividing them into districts:

• Condition 1. Each district contains houses whose $x$ coordinate is in a certain range. (A district might contain all or none of the houses)
• Condition 2. Each house is contained in exactly one district.
• Condition 3. There are at most $K$ districts.

There are diverse races, religions, and nations in the Eurasian Continent. To avoid disputes, we must reduce the “splittedness” of districts. The splittedness of a district is defined as the distance between the farthest pair of houses contained in the district. The distance is measured in Euclidean metric. Help jh05013 minimize the maximum splittedness among districts.

输入格式

In the first line, two space-separated integers $N, K$ are given. $N$ denotes the number of houses and $K$ denotes the number of districts.

In the next $N$ lines, two space-separated integers $x_i, y_i$ are given. They denote that a house is located at $(x_i, y_i)$.

输出格式

When the minimum of maximum splittedness among districts is $M$, print $M^2$.

4 2
101 100
2 5
100 101
4 3

8

4 4
3 1
4 1
5 1
9 2

0

提示

Constraints

• $1 \le K \le N \le 250,000$
• Every given location is distinct. It means, $i \ne j$ implies $x_i \ne x_j$ or $y_i \ne y_j$.
• $0 \le x_i, y_i \le 10^9$