bear-and-climbing-1

View Russian Translation

Limak is a brown bear.
Brown bears often climb trees and so does Limak.
As you probably know, bears use ropes to move between tops of trees.

There are N trees in a row.
i-th of them grows at coordinate X[i] and has height H[i].
A further tree is always higher - it's guaranteed that X[i] < X[i+1] and H[i] < H[i+1].

Limak is currently at the top of the first tree and he has a rope of length L.
He wants to be at the top of the last tree.
He can move from a-th to b-th tree if and only if all tree conditions are fulfilled:
1) a < b
2) (X[b]-X[a])^2 + (H[b]-H[a])^2 ≤ L - rope must be long enough
3) H[b]-H[a] < X[b]-X[a] - it's not safe to go very uphill

Note that there is no square root in the second condition.
The reason is that bears calculate distances a bit different than people.

Limak doesn't know if his rope is long enough.
Could you help him and calculate the minimum L for which he can get from the first tree to the last one?
Print -1 instead if there is no L for which Limak would reach the last tree.

Input format:

The first line contains one integer number N, denoting number of trees.
i-th of the next N lines contains two integer numbers X[i] and H[i], describing i-th tree.

Output format:

In the single line print the minimum possible L for which Limak would be able to get from the first to the last tree.
If there is no such L, print -1 instead.

Constraints:

2 ≤ N ≤ 10^6
1 ≤ X[i], H[i] ≤ 10^7
X[i] < X[i+1]
H[i] < H[i+1]

SAMPLE INPUT
4
3 2
4 3
13 4
15 5

SAMPLE OUTPUT
104

Explanation

Limak can't go to the second tree because inequality H[2]-H[1] < X[2]-X[1] doesn't hold.
With rope of length at least 10^2 + 2^2 = 104 he can go from the first to the third tree.
Then he needs rope of length at least 2^2 + 1^2 = 5 to get to the last tree.
So he can reach the last tree with L = 104.

Limak can also skip a third tree and go directly to the last one but he would need L = 12^2+3^2 = 153.

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions: