---

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）
  请在提交源代码前添加 #include "squirrel.h"。

---

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4「날다람쥐」

在二维平面上，有 $N$ 根柱子按顺序排列。柱子从左到右编号为 $1$ 到 $N$。第 $i$ $(1 \leq i \leq 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 \geq 0)$，高度会下降 $d$。在到达下一根柱子之前，飞天松鼠不能碰到地面。到达下一根柱子的高度为 $0$ 的位置是允许的。

飞天松鼠可以在一根柱子上向上爬或向下滑，但不能爬到超过柱子高度的位置。在第 $i$ 根柱子上向上爬 $h$ $(h \geq 0)$ 需要花费 $W_{i} \times h$ 的费用。向下滑动不需要费用。

下图是飞天松鼠移动的一个例子。

下图左侧的移动方式由于中途碰到地面，因此不允许。下图右侧的移动方式由于没有经过所有柱子，也不允许。

请计算飞天松鼠以最小总费用到达目标位置的方法。

---

实现细节

你需要实现以下函数：

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

• 该函数只会被调用一次。
• 给定的三个数组的大小为柱子的数量 $N$。
• 给定的整数数组 D 中，D[i] 表示第 $1$ 根柱子到第 $i+1$ 根柱子的距离 $D_{i+1}$。
• 给定的整数数组 H 中，H[i] 表示第 $i+1$ 根柱子的高度 $H_{i+1}$。
• 给定的整数数组 W 中，W[i] 表示第 $i+1$ 根柱子上每上升 $1$ 单位距离的费用 $W_{i+1}$。
• 给定的整数 $L$ 表示飞天松鼠在第 $1$ 根柱子上的初始高度。
• 给定的整数 $R$ 表示飞天松鼠在第 $N$ 根柱子上需要到达的高度。
• 该函数的返回值应为：
  • 如果有方法遵守规则到达最终位置，返回飞天松鼠到达最终位置的最小费用。可以证明，满足约束条件的输入数据的最小费用总是整数。
  • 如果没有方法遵守规则到达最终位置，返回 $-1$。

注意，提交的代码中不应包含任何输入输出操作。

---

样例

考虑 $N=3$，第 $1$ 根柱子到第 $2$ 根柱子的距离为 $2$，第 $1$ 根柱子到第 $3$ 根柱子的距离为 $5$，柱子的高度从左到右分别为 $8,5,5$，柱子的权重从左到右分别为 $3,4,6$，$L=5, R=4$ 的情况。

评测程序将调用如下函数：

fly([0, 2, 5], [8, 5, 5], [3, 4, 6], 5, 4) = 18

在这种情况下，从第 $1$ 根柱子上升 $2$ 个单位距离，然后在第 $3$ 根柱子上升 $2$ 个单位距离是最优的，因此函数应返回 $18$。

这个例子满足子任务 $3,4,5,6$ 的条件。

---

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5\cdot 10^5$
• $0=D_{1}<D_{2}<\cdots<D_{N} \leq 10^{9}$
• $1 \leq H_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $0 \leq W_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $0 \leq L \leq H_{1}$
• $0 \leq R \leq H_{N}$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	4	$W_{i}=0$ $(1 \leq i \leq N)$
2	13	$W_{i}=1$ $(1 \leq i \leq N)$
3	18	$W_{i} \leq W_{i+1}$ $(1 \leq i \leq N-1)$
4	15	$N \leq 500$；$H_{i} \leq 500$ $(1 \leq i \leq N)$
5	18	$N \leq 5000$
6	32	无附加限制

---

示例评测程序

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

• 第 $1$ 行：$N$
• 第 $1+i$ $(1 \leq i \leq N)$ 行：$D_{i}\,H_{i}\,W_{i}$
• 第 $2+N$ 行：$L\,R$

示例评测程序按以下格式输出：

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

示例评测程序可能与实际评测程序不同。