Bitcoin Mining Fields

Time limit1sMemory limit64 MB

Summary

Given up to a million integer points, find the largest squared Euclidean distance between any two of them and print it.

Level: Medium7 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

Bitcoin mining uses a lot of power. One day Ali and Betty decided to start their own mining fields in the center of Cheras, one field each. They went to Siva, the mayor of Cheras, to ask for locations.

Siva showed them a grid map with every possible location for a mining field. Mining draws a large amount of power, so Siva wants the two fields as far apart as possible to keep power spikes out of the neighbourhood.

Given the coordinates of all possible mining sites, find the largest Euclidean (straight line) distance between two of them. A site coordinate is always an integer.

Floating point arithmetic is easy to get slightly wrong, so you only have to output the square of that largest distance. The square of the Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as

$(x_1 - x_2)^2 + (y_1 - y_2)^2$

Input

The first line has the number of possible mining sites $N$ ( $2 \le N \le 10^6$ ).

The second line has $M$ ( $2 \le M \le 1500$ ), the largest absolute value a coordinate can take, so every site satisfies $-M \le x \le M$ and $-M \le y \le M$ .

Each of the next $N$ lines has two integers $X_i$ and $Y_i$ , the coordinates of one possible mining site. The same coordinate can appear more than once.

Output

Print the square of the Euclidean distance between the two farthest possible mining sites, as a single integer.

Examples7

Example 1
Input
```
2
15
-1 10
10 1
```
Expected output
```
202
```
Example 2
Input
```
3
15
1 10
2 10
10 10
```
Expected output
```
81
```
Example 3
Input
```
4
2
0 0
0 0
0 0
0 0
```
Expected output
```
0
```

Example 4

Input

5
1500
-1500 -1500
1500 1500
1500 -1500
-1500 1500
0 0

Expected output

18000000

Example 5
Input
```
4
10
-7 -10
-7 3
-7 10
-7 -4
```
Expected output
```
400
```
Example 6
Input
```
6
10
-10 0
10 0
-9 9
9 -9
0 0
3 -2
```
Expected output
```
648
```

Example 7

Input

Expected output