405987: GYM102202 E Water Knows the Answer

Donghyun lives in 2D plane, having $$$x$$$-axis as ground. It rains a lot in 2D plane, and the rain falls from $$$y = \inf$$$.

Recently, Donghyun read a book called "Water Knows the Answer", and got impressed by the book. He now believes that he will be super intelligent and smart if he has water with him.

Figure: The book "Water Knows the Answer".

Donghyun has $$$N$$$ rectangular boxes with (possibly) different heights and widths. He is going to rearrange those boxes in order to collect the rainfall. Then, the water will give him the answer. To achieve this, he have to place the box in a row. The ground absorbs the rainfall, so no empty space is allowed between the boxes. He may rotate some of the boxes or not, but he should make its edges parallel to the ground.

The water can flow to left or right, until it has space to flow. Formally, water in certain point can stay in its place if that point is not inside the box and has a box both somewhere to its left and somewhere to its right at the same height.

Donghyun wants to know the maximum area of water he can store. (In 2D plane, area means volume.) But, he doesn't have water yet, so he doesn't know the answer. Do you know the answer?

The first line contains an integer $$$N$$$, the number of boxes. ($$$3 \le N \le 250000$$$) For the next $$$N$$$ lines, $$$i$$$-th line contains two integer $$$w_i$$$ and $$$h_i$$$, the width and height of $$$i$$$-th box. ($$$1 \le w_i, h_i \le 10^6$$$)

Print a single integer, denoting the maximum area of water you can store if you arrange the boxes optimally.

3
4 3
2 6
5 1

15

Figure: Best arrangement for example input.