题目描述

Kalila 和 Dimna 是住在一片巨大森林中的两只豺狼。一天，他们决定去一家伐木厂打工来挣钱。

伐木厂的经理让他们去森林里砍倒 $n$ 棵树，这些树的高度分别为 $a_1, a_2, ..., a_n$。他们从商店买了一把电锯。每次用电锯锯编号为 $i$ 的树时，可以将这棵树的高度减少 $1$ 单位。每次 Kalila 和 Dimna 用完电锯，都需要为其充电一次。充电的花费取决于已经被完全砍倒的树的编号（当树的高度变为 $0$ 时，认为该树被完全砍倒）。如果当前为止被完全砍倒的树的最大编号是 $i$（即最初高度为 $a_i$ 的树），那么为电锯充电的花费为 $b_i$。如果没有树被完全砍倒，则 Kalila 和 Dimna 无法为电锯充电。电锯在开始时是充满电的。已知对于任意 $i<j$，$a_i < a_j$ 且 $b_i > b_j$ ，且 $b_n = 0$ ，$a_1 = 1$。Kalila 和 Dimna 想以最小的花费将所有的树全部砍倒。

他们需要你的帮助！你愿意帮助他们吗？

输入格式

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$）。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^{9}$）。

第三行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（$0 \leq b_i \leq 10^{9}$）。

保证 $a_1=1$，$b_n=0$，$a_1 < a_2 < \cdots < a_n$ 且 $b_1 > b_2 > \cdots > b_n$。

输出格式

输出一个整数，表示完全砍倒所有树的最小花费。

请不要在 C++ 中使用 %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