Water Knows the Answers

Can water think? Can it learn? After reading the book Water Knows the Answers: the Hidden Messages in Water Crystals, you may believe that water can reflect human emotions and has the power to listen, see, and know the answers to life.

Review of the book Water Knows the Answers by Masaru Emoto

Figure: The cover of the book Water Knows the Answers: the Hidden Messages in Water Crystals

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

Recently, Donghyun read Water Knows the Answers and was impressed by it. He now believes that water will tell him the answers to life.

Donghyun has $N$ rectangular boxes with possibly different heights and widths. He is going to rearrange them to collect the rainfall. Then the water will give him the answers to life. To do this, he places the boxes in a row. No empty space is allowed between the boxes. He may rotate some of the boxes or leave them as they are, but every box must have an edge touching the ground.

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

The figure below shows a possible example. The gray rectangles are boxes, and the blue regions are water.

What is the maximum area of water Donghyun can store? (In the 2D plane, area means volume.) He does not have water yet, so he does not know the answer. Do you know it?

The input consists of $N+1$ lines.

The first line contains the number of boxes $N$.

Each of the next $N$ lines contains the width $w_i$ and height $h_i$ of a box, separated by a space.

Print a single integer, the maximum area of water Donghyun can store when he arranges the boxes optimally.

• $3 \le N \le 250,000$
• $1 \le w_i,\ h_i \le 10^6$