Steel Slicing

ISCO (ICPC Steel Company) buys steel sheets of a certain shape, cuts them into pieces, and sells the pieces to the industry market. Every steel sheet ISCO buys is a polygon without holes, and each side is either horizontal or vertical with respect to the $x$-axis. The length of each side is a positive integer. We call such a polygon a histogon. Figure 1(a) shows a histogon.

Figure 1. (a) A steel sheet that is a histogon. (b) An axis-aligned rectangle (red) with maximum area contained in the histogon. (c) The histogon is subdivided along vertical lines into 8 rectangular slabs with width 1.

A piece sells for a much higher price when it is a rectangle with a larger area, so ISCO wants to cut each sheet to get a rectangle of maximum area. The task is to find the axis-aligned rectangle with the largest area that is contained in the steel sheet. The rectangle must have every side horizontal or vertical with respect to the $x$-axis. Figure 1(b) shows the maximum-area rectangle for the histogon in Figure 1(a).

A histogon with width $n$ can be subdivided along vertical lines into $n$ rectangular slabs with width 1. Figure 1(c) shows the histogon of Figure 1(a) split into 8 slabs. The slabs are numbered from 1 to $n$ from left to right, so the leftmost slab is number 1. Assume the $x$-axis intersects every slab. Slab $i$ is described by two values, $h_i$ and $l_i$, where $h_i$ is the vertical length of slab $i$ above the $x$-axis and $l_i$ is the vertical length of slab $i$ below the $x$-axis.

Given a histogon with width $n$, output the maximum area among the axis-aligned rectangles contained in the histogon.

The first line contains one integer $n$ ($1 \le n \le 200{,}000$), the width of the histogon. The slabs are numbered from 1 to $n$ such that the leftmost slab is number 1. Each of the following $n$ lines contains two nonnegative integers $h_i$ and $l_i$ ($0 \le h_i, l_i \le 1{,}000{,}000{,}000$) for slab $i$.

Print exactly one line containing the maximum area among the axis-aligned rectangles contained in the given histogon.