U. United States of Eurasia
time limit per test
20.0 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 (xi, yi) 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.

Input

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 xi, yi are given. They denote that a house is located at (xi, yi). ( 0 ≤ xi,  yi ≤ 109) Every given location is distinct.

Output

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

Examples
Input
4 2
101 100
2 5
100 101
4 3
Output
8
Input
4 4
3 1
4 1
5 1
9 2
Output
0