Будучи злым ученым, вы придумали, как создавать более крупных и страшных желе в своей секретной лаборатории. Вокруг вашего круглого лабораторного стола расположен циклический массив из $N$ прямоугольных желе, каждое из которых имеет определенную высоту и ширину. Заметьте, что первое и последнее желе являются соседними.

Иллюстрация слияния желе.

Вы можете объединить два соседних исходных желе, чтобы получить комбинированное желе с высотой, равной максимуму из высот двух исходных желе, и шириной, равной максимуму из ширин двух исходных желе. Полученное желе заменяет исходные на их месте в циклическом массиве (который теперь становится на один элемент короче) и в принципе может быть снова объединено с одним из своих соседей.

Вы хотите максимизировать сумму площадей ваших желе, выполнив эту операцию слияния любое количество раз. В конце концов, чем большую общую площадь могут покрыть ваши желе, тем больше городов вы сможете завоевать!

Входные данные

В первой строке входных данных содержится целое число $N$ ($1 \le N \le 3 \cdot 10^5$), количество желе, изначально находящихся на вашем лабораторном столе.

Следующие $N$ строк описывают эти желе в порядке их расположения. В $i$-й строке содержатся два целых числа, разделенных пробелом: $h_i$ и $w_i$ ($1 \le h_i, w_i \le 10^6$), высота и ширина $i$-го желе.

Выходные данные

Выведите единственное целое число: сумму площадей желе, которые останутся в вашем циклическом массиве после того, как вы выполните любое количество операций слияния для оптимальной максимизации этой суммы.

Примеры

Пример 1

2
6 3
2 7

42

Пример 2

4
1 5
10 10
5 1
6 7

152

Пример 3

5
6 2
5 1
1 5
2 7
1 2

67

Пример 4

1
380385 222650

84692720250