题目描述

一支勘探队从 $(0,0)$ 出发，终点是 $(0,y)$，携带着从 $1$ 号到 $n$ 号设备，每个设备的重量为 $m_i$，且必须安放在横坐标为 $x_i$ 的任意位置上（纵坐标可以是任意实数）。必须按照顺序安放所有设备，在较小编号的设备被全部放置之前，即使横坐标位置满足，也不能放置。

当勘探队身上的设备总重量为 $m$ 时，其移动一单位长度的代价是 $m+M$。问勘探队完成所有设备安装并到达终点的最小代价。

同一个坐标位置可以放置多台设备。

输入格式

输入第一行三个正整数 $n$ ($1\le n \le 1\times 10^4$)，$M$ ($0< M \le 30$) 和 $y$ ($0<y\le 2\times 10^5$)，代表设备个数、移动的基本代价和最终终点的纵坐标。

第二行给出 $n$ 个非负整数 $m_i$ ($0< m_i\le 30$)，表示第 $i$ 台设备的重量。两两之间用空格隔开。

第三行给出 $n$ 个整数 $x_i$ ($|x_i|\le 1\times 10^4$)，表示第 $i$ 台机器坐标的要求。

输出格式

输出一行一个正实数代表最终代价。如果你的答案是 $a$，我们给出的标准答案是 $b$，你的答案正确当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$。

1 25 14
14
12

882.000000

提示

走直线走到 $(12,5)$，距离 $13$，然后走直线走到 $(0,14)$，距离 $15$，总代价 $13\times (25+14)+15\times 25=882$。不存在一个比这个更优的解。