Problem Description

Do not submit using C++14 (GCC 9).

In the year 2992, robots have replaced most human work, and everyone has a lot of free time. Therefore, you and your family decide to use this time for an interstellar trip.

There are $N$ planets reachable by humans, numbered from $0$ to $N - 1$, and $M$ different interstellar train routes. The $i$-th train route ($0 \le i < M$) departs from planet $X[i]$ at time $A[i]$, arrives at planet $Y[i]$ at time $B[i]$, and costs $C[i]$. Between planets, these interstellar trains are the only means of transportation. For any interstellar train you take, you can only get off at its terminal station, and the departure planet of your next train must be the same as the arrival planet of the previous train (assume transfers take no time). Formally, you can take trains $q[0], q[1], \ldots, q[P]$ in order if and only if for every $1 \le k \le P$ we have $Y[q[k - 1]] = X[q[k]]$ and $B[q[k - 1]] \le A[q[k]]$.

Traveling between different planets is very time-consuming, so besides ticket costs, meal expenses cannot be ignored. Unlimited food is provided for free on trains, meaning eating on a train costs nothing: if you decide to take the $i$-th interstellar train, then at any moment between $A[i]$ and $B[i]$ (including endpoints) you may eat any number of meals for free. However, if you decide to eat on planet $i$, each meal costs $T[i]$.

During the trip, you and your family need to eat a total of $W$ meals. The $i$-th meal $(0 \le i < W)$ can be eaten at any time between $L[i]$ and $R[i]$ (including endpoints), and eating takes no time. There is no required order for meals; for example, it is allowed to eat meal $1$ before meal $0$ (see sample $2$).

It is now time $0$, and you and your family are on planet $0$. You need to find the minimum total cost to reach planet $N - 1$, where the cost is defined as the sum of ticket costs and meal costs. If it is impossible to reach planet $N - 1$, the minimum cost is defined as $-1$.

Implementation Details

You do not need to include the library train.h at the beginning of your program.

You only need to implement the following function:

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$: the number of planets.
• $M$: the number of interstellar train routes.
• $W$: the number of meals that must be eaten.
• $T$: an array of length $N$. $T[i]$ is the cost of each meal on planet $i$.
• $X, Y, A, B, C$: five arrays of length $M$. $(X[i], Y[i], A[i], B[i], C[i])$ describes the $i$-th train route.
• $L, R$: two arrays of length $W$. $(L[i], R[i])$ describes the time window of the $i$-th meal.
• You should return the minimum total cost to reach planet $N - 1$ from planet $0$. If planet $N - 1$ is unreachable, return $-1$.
• In each test case, this function is called exactly once.

Input Format

The sample grader reads input in the following format:

• Line $1$: $N\ M\ W$
• Line $2$: $T[0]\ T[1]\ T[2]\ \ldots\ T[N - 1]$
• Line $3 + i\ (0 \le i < M)$: $X[i]\ Y[i]\ A[i]\ B[i]\ C[i]$
• Line $3 + M + i\ (0 \le i < W)$: $L[i]\ R[i]$

Output Format

The sample grader prints your answer in the following format:

• Line $1$: the return value of the function 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

Hint

Sample Explanation

For sample 1, consider the following call:

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

One feasible plan is to take trains $0, 1$ in order, with a total cost of $45$. The detailed process is as follows:

A better plan is to take train $2$, with a total cost of $40$. The detailed process is as follows:

In this plan, eating meal $0$ on train $2$ at time $18$ is also valid.

Therefore, the function should return $40$.

For sample 2, consider the following call:

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});

The optimal solution is: take train $0$, with a ticket cost of $38$. Eat meal $1$ for free on train $0$. Eat meals $0, 2, 3$ on planet $2$, costing $33 \times 3 = 99$. Eat meals $4, 5$ on planet $0$, costing $30 \times 2 = 60$. The total cost is $38 + 99 + 60 = 197$.

Therefore, the function should return $197$.

Constraints

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

The detailed additional constraints and scores for subtasks are shown in the table below.

Translated by ChatGPT 5