Kalila 和 Dimna 是两只生活在巨大丛林中的豺狼。有一天,他们决定加入一家伐木厂来赚钱。
伐木厂经理要他们去丛林砍伐n棵高度为a1,a2,...,an的树。他们从商店买了一把链锯。每次他们在第 i 棵树上使用链锯时,他们就可以将这棵树的高度减少一个单位。卡利拉和迪姆纳每次使用链锯时都需要充电。收费成本取决于已被完全砍伐的树木的id(如果树的高度等于0则被完全砍伐)。如果一棵被完全砍伐的树的最大id是i(一开始的高度为ai的树),那么油锯充电的成本就是bi。如果没有树木被完全砍倒,卡利拉和迪姆纳就无法给链锯充电。电锯在开始时已充电。我们知道,对于每个 i < j,ai < aj 和 bi > bj,并且 bn = 0 且 a1 = 1。Kalila 和 Dimna 希望以最小的成本完全砍伐所有树木。
他们希望你帮助他们!你会?
输入
输入的第一行包含一个整数 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 说明符。
示例
输入 #1
5 1 2 3 4 5 5 4 3 2 0
输出 #1
25
输入 #2
6 1 2 3 10 20 30 6 5 4 3 2 0
输出 #2
138