题目描述

小P有$n$ 个牧场，自西向东呈一字形排列（自西向东用$1…n$ 编号），为了控制这$n$ 个牧场，他需要在某些牧场上建立控制站： 每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制；如果它西边不存在控制站，那么它控制西边所有的牧场）。 每个牧场被控制都需要一定的花费，而且该花费等于它到控制它的控制站之间的牧场数目（不包括自身，但包括控制站所在牧场）乘上该牧场的放养量。 在第$i$个牧场建立控制站的花费是$a_i$，每个牧场i的放养量是$b_i$。小P 需要总花费最小。

输入

第一行一个整数$n$ 表示牧场数目。 第二行包括$n$ 个整数，第$i$ 个整数表示$a_i$。 第三行包括$n$ 个整数，第$i$ 个整数表示$b_i$。

输出

只有一行，包括一个整数，表示最小花费。

输入样例

4
2 4 2 4
3 1 4 2

输出样例

9

提示

【样例解释】 选取牧场$1、3、4$建立控制站，最小费用为2+(2+1×1)+4=9。 【数据规模及约定】 对于20%的数据 : $1≤n≤10$。 对于40%的数据 : $1≤n≤1000$。 对于70%的数据 : $1≤n≤100000$。 对于100%的数据: 1≤n≤1000000；0 < a_i,b_i≤10000。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。