Вам надається тривимірна гістограма, яка складається з \(n\) блоків, які розміщені поруч один з одним. \(i\)-й блок має ширину 1 метр, висоту \(a_i\) метри та довжину \(b_i\) метри. Іншими словами, спереду це виглядає як гістограма зі стовпчиками висот \(a_1\), \(a_2\),. . ., \(a_n\), а зверху вона виглядає як гістограма з стовпчиками висотами \(b_1\), \(b_2\),. . ., \(b_n\).

Визначте блок з максимальним об'ємом, який можна розмістити всередині заданої тривимірної гістограми. Сторони цього блоку повинні бути паралельними сторонам блоків, з яких складається 3D-гістограма.

Формат вхідних даних

Перший рядок містить ціле число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) з опису завдання. Кожен \(i\)-й із наступних \(n\) рядків містить цілі числа \(a_i\) та \(b_i\) (\(1 \le a_i, b_i \le 10^6\)) з опису завдання.

При \(1 \le n \le 2000\) - 20 балів

при \(1 \le n \le 200000\) - 80 балів

Формат вихідних даних

Вивести шуканий об'єм у метрах кубічних

Приклад вхідних даних

5
5 3
4 4
2 1
3 2
1 5

Приклад вихідних даних

24

Примітка

На малюнку показана тривимірна гістограма з прикладу вхідних даних. Найбільший блок отримується за допомогою частин перших двох блоків, а він має ширину 2 метри, висоту 4 метри та довжину 3 метри. Об'єм цього блоку становить 2 x 4 x 3 = 24 куб.м.