405143: GYM101806 U United States of Eurasia

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. (1 ≤ K ≤ N ≤ 250, 000)

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). ( 0 ≤ x_i,  y_i ≤ 10⁹) Every given location is distinct.

When the minimum of maximum splittedness among districts is M, print M².

4 2
101 100
2 5
100 101
4 3

8

4 4
3 1
4 1
5 1
9 2

0