Kalila and Dimna in the Logging Industry

Kalila 和 Dimna 是生活在巨大丛林中的两只豺狗。有一天，他们决定加入伐木工厂来赚钱。 采伐工厂的经理希望他们去丛林砍伐高度为 $a_1,a_2,...,a_n$ 的 $n$ 棵树。他们从商店买了一把电锯。每次他们对编号为 $i$ 的树使用电锯，会使第 $i$ 个树的高度降低 $1$ 。每次 Kalila 和 Dimna 使用电锯后，他们都需要给它充电。 充电成本取决于已完全锯掉的树木的编号（树木高度等于 $0$ 时，我们说树木被完全锯掉 ）。如果已经被完全锯掉的树的最大编号是 $i$ ，则对电锯充电一次的成本将是 $b_i$ 。如果没有被完全锯掉的树木， Kalila 和 Dimna 将无法对电锯充电。电锯在开始时是充好电的。 保证对于任意 $i < j$ ，$a_i < a_j$ 且 $b_i > b_j$ 以及 $b_n = 0,a_1 = 1$ 。 Kalila 和 Dimna 想要以最低成本完全锯掉所有的树。 请你帮助他们计算这个最小代价。

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}&lt;a_{j} $ and $ b_{i}&gt;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?

The first line of input contains an integer $ n $ ( $ 1<=n<=10^{5} $ ). The second line of input contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ). The third line of input contains $ n $ integers $ b_{1},b_{2},...,b_{n} $ ( $ 0<=b_{i}<=10^{9} $ ). It's guaranteed that $ a_{1}=1 $ , $ b_{n}=0 $ , $ a_{1}&lt;a_{2}&lt;...&lt;a_{n} $ and $ b_{1}&gt;b_{2}&gt;...&gt;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.

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