Калила та Дімна — два шакали. Вони живуть у величезних джунглях. Якось шакали вирішили влаштуватися на завод лісозаготівлі та підробити.

Керуючий заводу хоче, щоб вони вирушили в джунглі і зрубали \(n\) дерев заввишки \(a_1, a_2, ... a_n\). Для цього Калила та Дімна купили ланцюгову пилку в магазині. Щоразу, коли вони використовують пилку на дереві номер \(i\), вони зменшують висоту цього дерева на одиницю. Щоразу Калила та Дімна мають заправити пилку для використання. Ціна заправки залежить від того, які дерева повністю спиляні (дерево вважається повністю спиляним, якщо його висота дорівнює 0). Якщо максимальний ідентифікатор повністю зрубаного дерева дорівнює \(i\) (спочатку це дерево мало висоту \(a_i\)), ціна заправки пили дорівнює \(b_i\). Якщо жодне дерево не зрубане повністю, то заправляти пилку забороняється. Спочатку пила заправлена. Відомо, що для кожного \(i < j\), \(a_i < a_j\) і \(b_i > b_j\), а також \(b_n = 0\) та \(a_1 = 1\).

Калила та Дімна хочуть повністю зрубати всі дерева з мінімальними витратами. Вони чекають на Вашу допомогу! Допоможете?

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

У першому рядку записано ціле число \(n\) (\(1 ≤ n ≤ 10^5\)).

У другому рядку записано \(n\) цілих чисел \(a_1, a_2, ..., a_n\) (\(1 ≤ a_i ≤ 10^9\)).

У третьому рядку записано \(n\) цілих чисел \(b_1, b_2, ..., b_n\) (\(0 ≤ b_i ≤ 10^9\)).

Гарантується, що \(a_1 = 1\), \(b_n = 0\), \(a_1 < a_2 < ... < a_n\) та \(b_1 > b_2 > ... > b_n\).

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

У єдиному рядку має бути записана мінімальна вартість вирубування всіх дерев.

Будь ласка, не використовуйте специфікатор %lld для читання або запису 64 бітових чисел на С++. Рекомендується використовувати потоки cin, cout або специфікатор %I64d.

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

5
1 2 3 4 5
5 4 3 2 0

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

25

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

6
1 2 3 10 20 30
6 5 4 3 2 0

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

138