题目描述

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

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

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

你和家人在旅途中总共需要吃 $W$ 顿饭，第 $i$ 顿饭 ($0 \leq 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$，具体流程如下：

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

在这种方案中，在时刻 $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 \leq N \leq 10^5$
• $0 \leq M, W \leq 10^5$
• $0 \leq X[i], Y[i] < N$, $X[i] \neq Y[i]$
• $1 \leq A[i] < B[i] \leq 10^9$
• $1 \leq T[i], C[i] \leq 10^9$
• $1 \leq L[i] \leq R[i] \leq 10^9$

子任务

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

评测程序示例

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

• 第 $1$ 行：$T$

对于接下来的 $T$ 组数据中的每一组：

• 第 $1$ 行：$N$ $M$ $W$
• 第 $2$ 行：$T[0]$ $T[1]$ $\ldots$ $T[N - 1]$
• 第 $3 + i\ (0 \leq i < M)$ 行：$X[i]$ $Y[i]$ $A[i]$ $B[i]$ $C[i]$
• 第 $3 + M + i\ (0 \leq i < W)$ 行：$L[i]$ $R[i]$

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

• 对于每组测试数据：
  • 第 $1$ 行：函数 solve 的返回值