题目描述

有一排楼房共 $n$ 栋，从左至右编号为 $1\sim n$

第 $i$ 座楼房的高度为 $h_i$，第 $i-1$ 栋楼房和第 $i$ 栋楼房之间距离为 $d_i$ 个单位

现要在楼房之间铺设水管，将水源从第 $1$ 栋楼楼顶运输至第 $n$ 栋楼楼顶

对于 $p<q$，如果修一条从 $p$ 楼楼顶到 $q$ 楼楼顶的水管，代价计算方法如下：

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

求将水源从第 $1$ 栋楼楼顶传输至第 $n$ 栋楼楼顶的最小代价

输入格式

输入共 $3$ 行

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

第二行共 $n-1$ 个整数，表示 $d_2,\ d_3,\ d_4,\ \dots,\ d_n$

第三行共 $n$ 个整数，表示 $h_1,\ h_2,\ h_3,\ \dots,\ h_n$

输出格式

一行一个整数，表示将水源从第 $1$ 栋楼楼顶传输至第 $n$ 栋楼楼顶的最小代价

样例数据

样例一

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

数据范围与约定

子任务编号	分值	特殊性质
$1$	$20$	$n\le 10$
$2$		$h_1\le h_2\le \dots\le h_k\ge h_{k+1}\ge h_{k+2}\ge\dots\ge h_n$，$\ d_2 = d_3 = \dots = d_n = 1,\ A=B$
$3$		$h_1\le h_2\le\dots\le h_n$
$4$	$40$	无

对于所有数据，有 $1\le n\le 1000$，$1\le h_i,d_i,A,B\le 10^6$