古丝绸之路包括起点和终点一共有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