在二维平面上，有 $N$ 根柱子排成一列。这些柱子从左到右依次编号为 $1$ 到 $N$。

第 $i$ ($1 \le i \le N$) 根柱子的底部位于点 $(D_i, 0)$，高度为 $H_i$。因此，该柱子是连接点 $(D_i, 0)$ 和 $(D_i, H_i)$ 的线段。此外，$D_1 = 0$。

起初，飞鼠位于最左侧柱子高度为 $L$ 的位置，即点 $(0, L)$。飞鼠想要按顺序经过所有柱子，最终到达最右侧柱子高度为 $R$ 的位置，即点 $(D_N, R)$。

当飞鼠从一根柱子飞向下一根柱子时，如果向右移动了 $d$ ($d \ge 0$) 的距离，高度会降低 $d$。在到达下一根柱子之前，它不能接触地面。允许到达下一根柱子高度为 $0$ 的位置。

飞鼠可以在一根柱子上向上爬或向下爬。它不能爬到高于柱子高度的位置。在第 $i$ 根柱子上向上爬 $h$ ($h \ge 0$) 的高度需要花费 $W_i \times h$ 的代价。从柱子上向下爬不需要任何代价。

下图 1 展示了飞鼠移动的一个示例。

图 1

像图 2 左侧那样的移动方式是不允许的，因为它在途中接触到了地面。像图 2 右侧那样的移动方式也是不允许的，因为它没有经过柱子。

图 2

请计算飞鼠到达目标位置所需的最小总代价。

实现细节

你需要实现以下函数：

long long fly(vector<int> D, vector<int> H, vector<int> W, int L, int R)

• 该函数仅会被调用一次。
• 作为参数传入的 3 个数组的大小均为柱子的数量 $N$。
• 作为参数传入的整数数组 $D$ 中，$D[i]$ 表示从第 $1$ 根柱子到第 $i+1$ 根柱子的距离 $D_{i+1}$。
• 作为参数传入的整数数组 $H$ 中，$H[i]$ 表示第 $i+1$ 根柱子的高度 $H_{i+1}$。
• 作为参数传入的整数数组 $W$ 中，$W[i]$ 表示在第 $i+1$ 根柱子上向上爬单位距离的代价 $W_{i+1}$。
• 作为参数传入的整数 $L$ 是飞鼠在第 $1$ 根柱子上的初始高度。
• 作为参数传入的整数 $R$ 是飞鼠在第 $N$ 根柱子上需要到达的高度。
• 该函数的返回值：
  • 如果存在符合规则到达最终位置的方法，则返回飞鼠到达最终位置的最小代价。可以证明，满足约束条件的输入数据下的最小代价始终为整数。
  • 如果不存在符合规则到达最终位置的方法，则返回 $-1$。

在提交的源代码中，不得执行任何输入输出函数。

数据范围

• $2 \le N \le 500\,000$
• $0 = D_1 < D_2 < \dots < D_N \le 10^9$
• $1 \le H_i \le 10^9$ ($1 \le i \le N$)
• $0 \le W_i \le 10^9$ ($1 \le i \le N$)
• $0 \le L \le H_1$
• $0 \le R \le H_N$

子任务

1. (4 分) $W_i = 0$ ($1 \le i \le N$)
2. (13 分) $W_i = 1$ ($1 \le i \le N$)
3. (18 分) $W_i \le W_{i+1}$ ($1 \le i \le N - 1$)
4. (15 分) $N \le 500$，$H_i \le 500$ ($1 \le i \le N$)
5. (18 分) $N \le 5\,000$
6. (32 分) 无额外约束。

说明

各子任务的得分为该子任务所有测试数据的得分中的最小值。

样例

输入格式 1

3
0 8 3
2 5 4
5 5 6
5 4

输出格式 1

18

说明

在这种情况下，最优方案是在第 $1$ 根柱子上向上爬 $2$ 个单位距离，并在第 $3$ 根柱子上向上爬 $2$ 个单位距离，因此函数应返回 $18$。该样例满足子任务 3, 4, 5, 6 的条件。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $1+i$ 行 ($1 \le i \le N$)：$D_i \ H_i \ W_i$
• 第 $2+N$ 行：$L \ R$

样例评测程序输出：

• 第 $1$ 行：函数 fly 的返回值

请注意，样例评测程序可能与实际评测时使用的评测程序不同。