Description

As an evil scientist, you have figured out how to create bigger and scarier jellies in your secret laboratory. Arranged around your circular lab bench is a $\emph{cyclic array}$ of $N$ rectangular jellies, each with a certain height and width. Note that the first and last jellies are adjacent.

You can fuse two adjacent parent jellies together to produce a combined jelly with height equal to the maximum of the two parent jelly heights and width equal to the maximum of the two parent jelly widths. The fused jelly replaces the parents at their spot in the cyclic array (which is now one element shorter) and could in principle be fused again with one of its two neighbors.

You want to maximize the sum of the areas of your jellies by performing this fusion operation any number of times. After all, the more total area your jellies can cover, the more cities you can conquer!

Input Format

The first line of input contains an integer $N$ $(1 \leq N \leq 3\cdot 10^5)$, the number of jellies initially on your lab bench.

The next $N$ lines describe these jellies, in order. The $i^\text{th}$ line contains two space-separated integers $h_i$ and $w_i$ $(1 \leq h_i, w_i \leq 10^6)$, the height and width of the $i^\text{th}$ jelly.

Output Format

Print a single integer: the sum of the areas of the jellies that remain in your cyclic array after you perform any number of fusion operations to optimally maximize this sum.

2
6 3
2 7

42

4
1 5
10 10
5 1
6 7

152

5
6 2
5 1
1 5
2 7
1 2

67

1
380385 222650

84692720250