题目背景

请勿使用 C++14(GCC9) 提交

在 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$ 行：$N\ M\ W$
• 第 $2$ 行：$T[0]\ T[1]\ T[2]\ \ldots\ T[N - 1]$
• 第 $3 + i\ (0 \le i < M)$ 行：$X[i]\ Y[i]\ A[i]\ B[i]\ C[i]$
• 第 $3 + M + i\ (0 \le i < W)$ 行：$L[i]\ R[i]$

输出格式

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

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

3 3 1 
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19

40

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

197

提示

样例解释

对于样例一，考虑如下调用：

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$。

对于样例二，考虑如下调用：

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$