Jako złowrogi naukowiec odkryłeś, jak tworzyć większe i bardziej przerażające galaretki w swoim tajnym laboratorium. Na okrągłym stole laboratoryjnym ułożonych jest w cyklicznej tablicy $N$ prostokątnych galaretek, każda o określonej wysokości i szerokości. Zauważ, że pierwsza i ostatnia galaretka są sąsiednie.

Możesz połączyć dwie sąsiednie galaretki rodzicielskie, aby uzyskać połączoną galaretkę o wysokości równej maksimum z wysokości obu galaretek rodzicielskich oraz szerokości równej maksimum z szerokości obu galaretek rodzicielskich. Połączona galaretka zastępuje rodziców w ich miejscu w cyklicznej tablicy (która jest teraz o jeden element krótsza) i w zasadzie może zostać ponownie połączona z jednym ze swoich dwóch sąsiadów.

Chcesz zmaksymalizować sumę pól powierzchni swoich galaretek, wykonując tę operację łączenia dowolną liczbę razy. W końcu im większą łączną powierzchnię mogą pokryć twoje galaretki, tym więcej miast możesz podbić!

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą $N$ ($1 \le N \le 3 \cdot 10^5$), liczbę galaretek znajdujących się początkowo na twoim stole laboratoryjnym.

Kolejne $N$ linii opisuje te galaretki w kolejności. $i$-ta linia zawiera dwie liczby całkowite oddzielone spacją $h_i$ oraz $w_i$ ($1 \le h_i, w_i \le 10^6$), wysokość i szerokość $i$-tej galaretki.

Wyjście

Wypisz pojedynczą liczbę całkowitą: sumę pól powierzchni galaretek, które pozostaną w twojej cyklicznej tablicy po wykonaniu dowolnej liczby operacji łączenia w celu optymalnego zmaksymalizowania tej sumy.

Przykład

Wejście 1

2
6 3
2 7

Wyjście 1

42

Wejście 2

4
1 5
10 10
5 1
6 7

Wyjście 2

152

Wejście 3

5
6 2
5 1
1 5
2 7
1 2

Wyjście 3

67

Wejście 4

1
380385 222650

Wyjście 4

84692720250