题目描述

小$\red{P }$在$\red{MC }$里有$\red{n }$个牧场，自西向东呈一字形排列（自西向东用$\red{1}$…$\red{n }$编号），于是 他就烦恼了：为了控制这$\red{n }$个牧场，他需要在某些牧场上面建立控制站，每个牧场上只 能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站 的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站， 那么它控制西边所有的牧场），每个牧场被控制都需要一定的花费（毕竟在控制站到牧 场间修建道路是需要资源的嘛~），而且该花费等于它到控制它的控制站之间的牧场数目 （不包括自身，但包括控制站所在牧场）乘上该牧场的放养量，在第$\red{i }$个牧场建立控制 站的花费是$\red{ai，}$每个牧场$\red{i }$的放养量是$\red{bi，}$理所当然，小$\red{P }$需要总花费最小，但是小$\red{P}$ 的智商有点不够用了，所以这个最小总花费就由你来算出啦。

输入格式

第一行一个整数$\red{n }$表示牧场数目

第二行包括$\red{n }$个整数，第$\red{i }$个整数表示$\red{ai}$

第三行包括$\red{n }$个整数，第$\red{i }$个整数表示$\red{bi}$

输出格式

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

样例

输入样例

4
2 4 2 4
3 1 4 2

输出样例

9

提示

选取牧场$\red{1，}$$\red{3，}$$\red{4 }$建立控制站，最小费用为$\red{2+( 2 + 1 * 1 ) + 4 = 9}$。

数据范围与约定

对于$\red{10\%}$的数据，$\red{1 <= n <= 10}$

对于$\red{30\%}$的数据，$\red{1 <= n <= 1000}$

对于$\red{100\%}$的数据，$\red{1 <= n <= 1000000 , 0 < ai,bi <= 10000}$