Minimum Height Watchtower

Village chief dadzhi wants to construct a watchtower in the village H so that from the top of the tower one can see every location in the village. The village is modeled as a one‐dimensional mountain profile given by a polyline with vertices \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\) where \(x_1 < x_2 < \cdots < x_n\). The watchtower can be built at any position \(t\) with \(x_1 \le t \le x_n\), but its top must have a high enough elevation \(H\) so that the line of sight from \((t, H)\) reaches every vertex without being blocked by the mountain itself.

More formally, when the tower is built at position \(t\) with tower top at \((t,H)\), the watchtower is considered to have an unobstructed view of the village if for every vertex \((x_i,y_i)\) the line segment connecting \((t,H)\) and \((x_i,y_i)\) does not pass below the mountain profile. In this problem the mountain profile is given by the vertices and the connecting line segments. To save on cost, dadzhi wants the watchtower to be as low as possible while still satisfying the condition that every vertex is visible from the top.

Observation and Approach:

A useful observation is that if we decide to build the watchtower directly underneath one of the vertices, say at \(x_i\), then the minimum required tower height is forced by the conditions on both sides:

• Left side: Starting from the leftmost vertex \((x_1,y_1)\) and moving right, in order for the tower at \(x_i\) to see every vertex on its left, the tower top must be at least high enough so that when progressing from one vertex to the next the required height increases by at least the horizontal difference. We can define an array left where left[0] = y_1 and for each subsequent vertex left[i] = max(y[i], left[i-1] + (x[i] - x[i-1])).
• Right side: Similarly, from the rightmost vertex \((x_n,y_n)\) moving leftwards, define an array right where right[n-1] = y_n and for each previous vertex right[i] = max(y[i], right[i+1] + (x[i+1] - x[i])).

The minimum height if the watchtower is built exactly at \(x_i\) is then max(left[i], right[i]). By trying all vertices, the optimal solution is the minimal such value. Note that even though the watchtower can be built at an arbitrary \(t\) in \([x_1,x_n]\), it can be shown that an optimal solution is achieved when \(t\) coincides with one of the \(x_i\)'s.

Your task is to compute the minimal tower height required.

inputFormat

The first line contains an integer \(n\) (\(n \ge 3\)), the number of vertices describing the mountain profile. Each of the following \(n\) lines contains two integers \(x_i\) and \(y_i\) (\(0 \le x_i, y_i \le 10^9\)) with \(x_1 < x_2 < \cdots < x_n\).

outputFormat

Output a single integer, the minimum height \(H\) required for the watchtower.

sample

3
1 3
2 4
3 3

4