309001 - 丝绸之路

古丝绸之路包括起点和终点一共有N+1个城市,0号城市是起点长安,N号城市是终点巴格达。商队一天的时间可以从一个城市到连续的下一个城市,从i-1城市到i城市距离是D_i,商队在M天内必须到达终点。

沙漠天气变化无常,在天气很不好时,前进会遇到很多困难。我们把第j(1\le j\le M)天的气候恶劣值记为C_j,在第j天从i-1城市移动到i城市需要耗费D_i×C_j的疲劳度。

所以商队在一个城市时,可以有两种选择:

(1)移动:向下一个城市进发;

(2)休息:呆在这个城市不动,没有疲劳度。

试求整个行程最少要消耗多少疲劳值。

输入

第一行2个整数N,M(1\le N,M\le1 000)

第二行N个整数,表示距离D_i(1\le D_i\le1 000)

第三行M个整数,表示气候恶劣值C_j(1\le C_j\le1 000)

输出

输出整个行程最少疲劳值。

样例

输入

3 5
10 25 15
50 30 15 40 30

输出

1125

提示

0+10×30+25×15+0+15×30=1125

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题