Виріб виготовляють з \(N\) блоків, кожен який має два параметри \(Hi, Wi\) (висоту і ширину).
Відомо, що висота кожного блока, дорівнює ширині попереднього блока.

Якщо два сусідніх блоки з параметрами (A,B) та (B,C) з'єднуються в один - вони утворюють блок з параметрами (A,C) і ця операція коштує A*C гривень.

Новий блок можна об'єднувати з іншими сусідніми, і так далі.
Ціна виготовлення виробу залежиться від порядку з'єднання блоків.

Наприклад, є блоки з параметрами (34,29), (29,4), (4,15).

Якщо спочатку з'єднати блоки (29,4), (4,15) - це буде коштувати 29*15 гривень, і отримаємо блок (29,15), а потім з'єднаємо блок (34,29) + (29,15) - це буде коштувати 34*15 і отримаємо блок (34,15).
Загальна вартість виготовлення: 29*15 + 34*15 = 945 грн

А якщо спочатку з'єднати блоки (34,29)+(29,4) - витратимо 34*4 гривені, та отримаємо блок (34,4) який далі з'єднаємо з блоком (4,15) заплативши 34*15 грн, і отримаємо в результаті блок (34,15).
Загальна вартість цього варіанту 34*4+34*15=646 грн

Напишіть програму, яка знайде мінімальну вартість виготовлення виробу.

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

Перший рядок містить число число \(N\) - кількість блоків (\(1 \le N \le 100\)).
Наступні \(N\) рядків містять по два числа - параметри блоків \(Hi, Wi\) (0 \le Hi, Wi \le 100~)

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

Виведіть єдине число - мінімальну вартість розпилювання.

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

3
34 29
29 4
4 15

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

646