CF319C.Kalila and Dimna in the Logging Industry

Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money.

The manager of logging factory wants them to go to the jungle and cut n trees with heights _a_1, _a_2, ..., a__n. They bought a chain saw from a shop. Each time they use the chain saw on the tree number i, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is i (the tree that have height a__i in the beginning), then the cost of charging the chain saw would be b__i. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each i < j, a__i < a__j and b__i > b__j and also b__n = 0 and _a_1 = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost.

They want you to help them! Will you?

卡莉拉和迪姆纳是生活在一片广阔丛林中的两只豺狼。一天，它们决定加入一家伐木工厂以赚钱。

伐木工厂的经理要求它们前往丛林砍伐 $n$ 棵树，这些树的初始高度分别为 $a_1,\,a_2,\,\dots,\,a_n$。它们从一家商店购买了一台链锯。每次对第 $i$ 棵树使用链锯，该树的高度便减少 1 个单位。每次卡莉拉和迪姆纳使用链锯后，都需要为其充电。充电成本取决于已被完全砍倒的树的编号（一棵树被完全砍倒当且仅当其当前高度为 0）。若已被完全砍倒的树中编号最大的为 $i$（即初始高度为 $a_i$ 的那棵树），则此次链锯充电的成本为 $b_i$。若尚无任何树被完全砍倒，则卡莉拉和迪姆纳无法为链锯充电。链锯在初始时已充满电。已知：对任意 $i < j$，均有 $a_i < a_j$ 且 $b_i > b_j$；此外，$b_n = 0$ 且 $a_1 = 1$。卡莉拉和迪姆纳希望以最小总成本将所有树全部砍倒。

它们希望你帮助它们！你愿意吗？

The first line of input contains an integer n (1 ≤ n ≤ 105). The second line of input contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109). The third line of input contains n integers _b_1, _b_2, ..., b__n (0 ≤ b__i ≤ 109).

It's guaranteed that _a_1 = 1, b__n = 0, _a_1 < _a_2 < ... < a__n and _b_1 > _b_2 > ... > b__n.

输入的第一行包含一个整数 $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 < ... < a_n$，且 $b_1 > b_2 > ... > b_n$。

The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出仅有一行，必须包含完全砍伐所有树木的最小花费。

请注意，在 C++ 中不要使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。