Intergalactic Dining Journey

In this problem, you are given a set of planets and interstellar train routes between them. You are required to travel from planet $0$ to planet $N-1$ while having exactly $W$ meals. Each planet $i$ charges a dining cost of $T_i$ per meal. In addition, there are $M$ train routes. The $i$-th route is described by the tuple $(X_i, Y_i, A_i, B_i, C_i)$, where the route goes from planet $X_i$ to planet $Y_i$ with a cost of $C_i$ (the parameters $A_i$ and $B_i$ represent schedule parameters but do not affect the cost computation in this problem). The $W$ meals have to be taken at specific time windows. The $i$-th meal must be consumed during the time interval $[L_i, R_i]$ (both endpoints inclusive). You do not need to worry about the time windows while coding and you should simply assume that you can dine on any planet you pass. In other words, the extra dining cost incurred is $W \times \min_{0 \le i < N} T_i$, because you can always choose the planet with the smallest dining cost for your meals.

Your task is to compute the minimum total cost which is defined as the sum of the cost of the chosen train routes plus the dining cost, i.e.

[ \text{Total Cost} = \text{(sum of route costs on a valid path from }0\text{ to }N-1) + W \times \min_{0 \le i < N} T_i. ]

If planet $N-1$ is unreachable from planet $0$, return $-1$.

Note: You do not need to include the header file train.h in your submitted code.

You only need to implement the 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);

Each test case calls this function exactly once.

inputFormat

The input is provided as follows:

1. Three integers: $N$ (number of planets), $M$ (number of train routes), and $W$ (number of meals).
2. An array of $N$ integers: $T$, where $T[i]$ is the meal cost at planet $i$.
3. For the $M$ train routes, 5 arrays are given:
   • An array $X$ of length $M$ (starting planet of each route).
   • An array $Y$ of length $M$ (destination planet of each route).
   • An array $A$ of length $M$ (schedule parameter, not used in cost computation).
   • An array $B$ of length $M$ (schedule parameter, not used in cost computation).
   • An array $C$ of length $M$ (cost of the corresponding train route).
4. For the $W$ meals, two arrays are given:
   • An array $L$ of length $W$ (start times for meal intervals).
   • An array $R$ of length $W$ (end times for meal intervals).

The test case input is given as multiple lines where each line contains one or several integers.

outputFormat

Output a single integer which is the minimum total cost to travel from planet $0$ to planet $N-1$. The total cost equals the sum of the costs of the selected train routes along the path plus the dining cost which is computed as $W \times \min_{0 \le i < N} T_i$. If there is no valid path from planet $0$ to planet $N-1$, output $-1$.

sample

2 1 1
5 10
0
1
0
10
3
0
20

8