#YDRB002D. 水管

水管

题目描述

有一排楼房共 nn 栋,从左至右编号为 1n1\sim n

ii 座楼房的高度为 hih_i,第 i1i-1 栋楼房和第 ii 栋楼房之间距离为 did_i 个单位

现要在楼房之间铺设水管,将水源从第 11 栋楼楼顶运输至第 nn 栋楼楼顶

对于 p<qp<q,如果修一条从 pp 楼楼顶到 qq 楼楼顶的水管,代价计算方法如下:

  • 如果 hp>hqh_p > h_q,则水会自然流下,每运输单位水平距离代价为水管费用 AA
  • 否则需要水泵向上泵水,每运输单位水平距离代价为 hqhp+Bh_q - h_p +B

求将水源从第 11 栋楼楼顶传输至第 nn 栋楼楼顶的最小代价

输入格式

输入共 33

第一行三个整数 n, A, Bn,\ A,\ B

第二行共 n1n-1 个整数,表示 d2, d3, d4, , dnd_2,\ d_3,\ d_4,\ \dots,\ d_n

第三行共 nn 个整数,表示 h1, h2, h3, , hnh_1,\ h_2,\ h_3,\ \dots,\ h_n

输出格式

一行一个整数,表示将水源从第 11 栋楼楼顶传输至第 nn 栋楼楼顶的最小代价

样例数据

样例一

input

5 1 1
1 1 1 1
5 13 17 11 10

output

12

样例二

input

5 10 9
11 4 15 20
12 15 6 19 5

output

500

样例三

input

20 68 87
46 3 73 37 75 80 7 94 100 72 2 53 85 3 41 15 34 74 83
8 78 24 24 24 61 94 20 76 1 74 7 38 23 38 76 44 74 86 99

output

75480

数据范围与约定

子任务编号 分值 特殊性质
11 2020 n10n\le 10
22 $h_1\le h_2\le \dots\le h_k\ge h_{k+1}\ge h_{k+2}\ge\dots\ge h_n$, d2=d3==dn=1, A=B\ d_2 = d_3 = \dots = d_n = 1,\ A=B
33 h1h2hnh_1\le h_2\le\dots\le h_n
44 4040

对于所有数据,有 1n10001\le n\le 10001hi,di,A,B1061\le h_i,d_i,A,B\le 10^6