#214505. [JOISC 2017] 长途巴士 / Long Distance Coach

在城市 I 与城市 O 之间有一辆长途客车，车上配备了一台供水机，乘客和司机均可从中取水饮用。客车于时间 从城市 I 出发，于时间 抵达城市 O。沿途共有 个补水点，客车在第 个补水点（）的到达时间为 。

初始时，供水机内无水。我们可以在出发前向供水机注水；此外，当客车停靠在补水点时，也可向供水机注水。无论客车处于何处，每升水的价格均为 日元。

在城市 I，有 名乘客上车，乘客编号为 至 。除城市 I 外，其他地点无乘客上车。第 名乘客（）在时间 需要一升水。若他饮水，则在经过时间 后将再次需要一升水。换言之，第 名乘客在时间 （）需要水。此处满足 ，且所有乘客的 值相同。若供水机在乘客需要水时无水，则该乘客将离开客车。若第 名乘客在抵达城市 O 前离开客车，我们需要退还其车费，退款费用为 日元。

司机同样需要饮水。若他饮水，则在经过时间 后将再次需要一升水，方式与乘客相同。换言之，司机在时间 （）需要水。若供水机在司机需要水时无水，则客车运营将停止。

不会同时有两人需要水。当客车抵达城市 O 或补水点时，乘客和司机均不需要水。

通过调整在补水点向供水机注水的水量，我们希望最小化水费与退款费用之和，并确保客车能够顺利运营至城市 O。你的任务是决定在旅途中于何处、注入多少水量至供水机。

任务

给定客车的行驶时间、补水点信息、乘客与司机的需求信息，编写一个程序，计算在客车成功抵达城市 O 的前提下，水费与退款费用之和的最小值。

从标准输入读取以下数据：

• 输入的第一行包含五个以空格分隔的整数 、、、、。这表示客车将在时间 抵达城市 O，沿途有 个补水点，车上共有 名乘客，每升水的价格为 日元，乘客与司机的饮水间隔时间为 。
• 接下来的 行中，第 行（）包含一个整数 ，表示客车将在时间 到达第 个补水点。
• 接下来的 行中，第 行（）包含两个以空格分隔的整数 、，表示第 名乘客首次需要水的时间为 ，且为其退款的费用为 。

向标准输出写入一行。输出包含一个整数，表示最小总费用。

样例输入 1

19 1 4 8 7
10
1 20
2 10
4 5
6 5

样例输出 1

103

样例输入 2

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

样例输出 2

547

样例输入 3

1000000000000 1 1 1000000 6
999999259244
1 123456789

样例输出 3

333333209997456789

样例 1 解释

在本样例输入中，若我们在出发前向供水机注入 7 升水，并在第一个补水点注入 4 升水，则客车的运行过程如下：

1. 客车从城市 I 出发。此时，供水机内有 7 升水。
2. 司机与乘客 1、2、3、4 分别在时间 、、、、 饮用 1 升水。剩余水量为 2 升。
3. 司机与乘客 1 分别在时间 、 饮用 1 升水。剩余水量为 0 升。
4. 在时间 ，乘客 2 需要水，但由于供水机无水，他离开客车。
5. 在时间 ，我们在第一个补水点向供水机注入 4 升水。剩余水量为 4 升。
6. 乘客 3、4、司机与乘客 1 分别在时间 、、、 饮用 1 升水。剩余水量为 0 升。
7. 在时间 ，乘客 3 需要水，但由于供水机无水，他离开客车。
8. 在时间 ，客车抵达城市 O。

总共用水量为 11 升，水费为 88 日元。乘客 2 与乘客 3 的退款费用之和为 15 日元。总费用为 103 日元。

我们输出 103，因为若总费用小于或等于 102 日元，则无法使客车正常运行。

数据范围

所有输入数据均满足以下条件：

• 。
• 。
• 。
• 。
• 。
• （）。
• （）。
• （）。
• （）互不相同。
• 当客车抵达城市 O 或补水点时，乘客与司机均不需要水。

子任务

共有 4 个子任务。每个子任务的得分及额外约束如下：

子任务 1 [16 分]

• 。
• 。

子任务 2 [30 分]

• 。
• 。

子任务 3 [25 分]

• 。
• 。

子任务 4 [29 分]

无额外约束。

翻译由 Qwen3-235B 完成