C. Калила и Димна на лесозаготовках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Управляющий завода хочет, чтобы они отправились в джунгли и срубили n деревьев высотой a1, a2, ..., an. Для этого Калила и Димна купили цепную пилу в магазине. Каждый раз, когда они используют пилу на дереве номер i, они уменьшают высоту этого дерева на единицу. Каждый раз Калила и Димна должны заправить пилу для использования. Цена заправки зависит от того, какие деревья полностью спилены (дерево считается полностью спиленным, если его высота равна 0). Если максимальный идентификатор полностью срубленного дерева равняется i (первоначально это дерево имело высоту ai), то цена заправки пилы равняется bi. Если ни одно дерево не срублено полностью, то заправлять пилу запрещается. Изначально пила заправлена. Известно, что для каждого i < j, ai < aj и bi > bj, а также bn = 0 и a1 = 1.

Калила и Димна хотят полностью срубить все деревья с минимальными затратами. Они ждут Вашей помощи! Поможете?

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

В первой строке записано целое число n (1 ≤ n ≤ 105). Во второй строке записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109). В третьей строке записано n целых чисел b1, b2, ..., bn (0 ≤ bi ≤ 109).

Гарантируется, что a1 = 1, bn = 0, a1 < a2 < ... < an и b1 > b2 > ... > bn.

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

В единственной строке должна быть записана минимальная стоимость вырубания всех деревьев.

Пожалуйста, не используйте спецификатор %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