---

4161. 「APIO2024」星际列车

时间限制：$1000 \text{ ms}$
内存限制：$1024 \text{ MiB}$

题目描述

在 $2992$ 年，机器人已经取代了人类的大部分工作，大家都有着大量的空闲时间。因此你和家人决定利用这些时间来一场星际旅行。

有 $N$ 个人类已经可以到达的行星，编号为 $0$ 到 $N - 1$，以及 $M$ 种不同的星际列车路线。第 $i$ 种列车路线 $(0 \le i < M)$ 在时间 $A[i]$ 从行星 $X[i]$ 出发，在时间 $B[i]$ 到达行星 $Y[i]$，票价为 $C[i]$。在行星之间，这些星际列车是仅有的交通方式。对于你搭乘的一列星际列车，你只能在它的终点站下车，并且你搭乘的下一趟列车的起点站必须和这趟列车的终点站相同（这里认为换乘不耗时）。形式化地，你可以依次乘坐第 $q[0], q[1], \ldots, q[P]$ 次列车，当且仅当对任意 $1 \le k \le P$ 都有 $Y[q[k - 1]] = X[q[k]]$，$B[q[k - 1]] \le A[q[k]]$。

在不同行星之间移动是非常耗时的，所以除了车票钱，餐费支出也不可忽视。列车上免费提供不限量的食物，也就是在列车上吃饭不花钱：如果你决定乘坐第 $i$ 种星际列车，则在任何 $A[i]$ 到 $B[i]$ 之间的时刻（包括端点）你都可以免费吃任意多顿饭。但如果你决定在行星 $i$ 吃饭，每顿饭都需要 $T[i]$ 元。

你和家人在旅途中总共需要吃 $W$ 顿饭，第 $i$ $(0 \le i < W)$ 顿饭可以在 $L[i]$ 到 $R[i]$（包括端点）的任何时刻吃，吃饭不耗费时间。吃饭没有顺序要求，例如允许在吃完第 $1$ 顿饭后再吃第 $0$ 顿饭（见样例 2）。

现在是 $0$ 时刻，你和家人正在 $0$ 号行星上。你需要求出到达 $N - 1$ 号行星的最小花费，花费定义为车票价格和餐费之和。如果无法到达 $N - 1$ 号行星，最小花费定义为 $-1$。

---

实现细节

请在程序开头引入库 train.h。

你需要实现以下函数：

long long solve(int N, int M, int W, std::vector<int> T,
                std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C,
                std::vector<int> L, std::vector<int> R);

• N：行星数量。
• M：星际列车路线数量。
• W：需要用餐的次数。
• T：一个长度为 $N$ 的数组。$T[i]$ 表示在行星 $i$ 每次用餐的花费。
• X, Y, A, B, C：五个长为 $M$ 的数组。$(X[i], Y [i], A[i], B[i], C[i])$ 描述了第 $i$ 条列车路线。
• L, R：两个长为 $W$ 的数组。$(L[i], R[i])$ 描述了第 $i$ 顿饭的用餐时间。

你需要返回从行星 $0$ 到达行星 $N - 1$ 的最小花费。如果行星 $N - 1$ 不可达，返回 $-1$。

每个测试点中，该函数恰好被调用一次。

---

样例 1

考虑如下调用：

solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
        {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});

一种可行的方案是依次乘坐第 $0, 1$ 次列车，花费为 $45$，具体流程如下：

时刻	你的行动	花费
$1$	乘坐第 $0$ 次列车从 $0$ 号行星出发	$10$
$15$	到达 $1$ 号行星
$16$	在 $1$ 号行星吃第 $0$ 顿饭	$30$
$20$	乘坐第 $1$ 次列车从 $1$ 号行星出发	$5$
$30$	到达 $2$ 号行星

一种更优的方案是乘坐第 $2$ 次列车，花费为 $40$，具体流程如下：

时刻	你的行动	花费
$18$	乘坐第 $2$ 次列车从 $0$ 号行星出发	$40$
$19$	在第 $2$ 次列车上吃第 $0$ 顿饭
$40$	到达 $2$ 号行星

在这种方案中，在时刻 $18$ 在第 $2$ 次列车上吃第 $0$ 顿饭也是合法的。

因此函数应该返回 $40$。

---

样例 2

考虑如下调用：

solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
        {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
        {32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5});

最优解是：乘坐第 $0$ 次列车，车费为 $38$。在第 $0$ 次列车上免费吃第 $1$ 顿饭。第 $0, 2, 3$ 顿饭在行星 $2$ 上吃 ，花费 $33 \times 3 = 99$。 第 $4, 5$ 顿饭在行星 $0$ 上吃，花费 $30 \times 2 = 60$。总花费为 $38 + 99 + 60 = 197$。

因此函数应该返回 $197$。

---

约束条件

• $2 \le N \le 10^5$
• $0 \le M, W \le 10^5$
• $0 \le X[i], Y [i] < N$，$X[i] \neq Y[i]$
• $1 \le A[i] < B[i] \le 10^9$
• $1 \le T[i], C[i] \le 10^9$
• $1 \le L[i] \le R[i] \le 10^9$

---

子任务

子任务编号	附加限制	分值
1	$N, M, A[i], B[i], L[i], R[i] \le 10^3$，$W \le 10$	$5$
2	$W = 0$
3	每顿饭的用餐时间两两不交。形式化地，对于任何时刻 $z$ 满足 $1 \le z \le 10^9$，至多存在一个 $i$ $(0 \le i < W)$ 使得 $L[i] \le z \le R[i]$。	$30$
4	没有额外的约束条件	$60$

---

评测程序示例

评测程序示例读取如下格式的输入：

第 1 行：N M W
第 2 行：T[0] T[1] T[2] ... T[N - 1]
第 3 + i (0 ≤ i < M) 行：X[i] Y[i] A[i] B[i] C[i]
第 3 + M + i (0 ≤ i < W) 行：L[i] R[i]

评测程序示例按照如下格式打印你的答案：

第 1 行：函数 solve 的返回值