P6772 [NOI2020] Gourmet

After the Elf Kingdom on the continent of Bzeroth repelled the invasion of the Catastrophe Legion, it spent more than ten years recovering and once again became a thriving paradise that attracts visitors from all directions. Little W is a famous gourmet who has traveled around the world, and he has now come to the Elf Kingdom by reputation. The Elf Kingdom has $n$ cities, numbered from $1$ to $n$. The food in city $i$ can provide Little W with $c_i$ happiness. The cities are connected by $m$ **directed roads**, numbered from $1$ to $m$. For road $i$, its start city is $u_i$, its end city is $v_i$, and traveling along it takes $w_i$ days. That is, if Little W travels from city $u_i$ along road $i$ on day $d$, then he will arrive at city $v_i$ on day $d + w_i$. Little W plans a trip in the Elf Kingdom lasting $T$ days. More specifically: he will set off from city $1$ on day $0$, and after $T$ days of travel, he will return to city $1$ on **exactly day $T$** to end the trip. Since Little W is a gourmet, every time he arrives at a city (including city $1$ on day $0$ and day $T$), he will taste the food of that city and gain the happiness it provides. If Little W arrives at the same city multiple times, he will **gain happiness multiple times**. Note that during the trip, Little W **cannot stay in any city**. That is, when he arrives at a city and the trip has not ended yet, he must depart immediately on the same day to another city.  For the figure above, one feasible travel plan of length $11$ days is $1 \to 2 \to 1 \to 2 \to 3 \to 1$: - On day $0$, Little W starts the trip from city $1$, gains happiness $1$, and departs for city $2$. - On day $1$, Little W arrives at city $2$, gains happiness $3$, and departs for city $1$. - On day $4$, Little W arrives at city $1$, gains happiness $1$, and departs for city $2$. - On day $5$, Little W arrives at city $2$, gains happiness $3$, and departs for city $3$. - On day $7$, Little W arrives at city $3$, gains happiness $4$, and departs for city $1$. - On day $11$, Little W arrives at city $1$, gains happiness $1$, and ends the trip. - The total happiness gained in this trip is $13$. In addition, the Elf Kingdom will hold $k$ food festivals at **different** times. Specifically, the $i$-th food festival will be held in city $x_i$ on day $t_i$. If Little W is in city $x_i$ on day $t_i$, then when he tastes the food in city $x_i$, he will gain an **extra** $y_i$ happiness. Now Little W asks you, as the reception envoy of the Elf Kingdom, to help him compute the **maximum** possible total happiness he can gain during the trip.

Read data from standard input. The first line contains four integers $n, m, T, k$, representing the number of cities, the number of roads, the travel days, and the number of food festivals. The second line contains $n$ integers $c_i$, representing the happiness provided by the food in each city. Then follow $m$ lines, each containing three integers $u_i, v_i, w_i$, representing the start city, end city, and travel days of each road. Finally, there are $k$ lines, each containing three integers $t_i, x_i, y_i$, representing the time, city, and extra happiness provided by each food festival. The testdata guarantees: - For all $1 \leq i \leq m$, $u_i \neq v_i$. However, the testdata may contain multiple directed roads with the same route, i.e. there may exist $1 \leq i < j \leq m$ such that $u_i = u_j$ and $v_i = v_j$. - For every city, there exists at least one directed road starting from that city. - The times $t_i$ of all food festivals are pairwise distinct.

Output to standard output. Output a single integer in one line, representing the maximum total happiness Little W can obtain through traveling. **If Little W cannot return to city $1$ on day $T$, output $-1$.**

#### Explanation for Sample 1 This sample is the example in the statement. The optimal travel plan is shown in the statement. #### Explanation for Sample 2 The optimal plan is $1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1$. - On day $0$, Little W starts the trip from city $1$, gains happiness $3$, and travels along road $3$. - On day $2$, Little W arrives at city $3$, gains happiness $2$, and travels along road $4$. - On day $5$, Little W arrives at city $4$, gains happiness $20 + 4$ due to the food festival, and travels along road $7$. - On day $6$, Little W arrives at city $2$, gains happiness $1$, and travels along road $5$. - On day $8$, Little W arrives at city $3$, gains happiness $2$, and travels along road $4$. - On day $11$, Little W arrives at city $4$, gains happiness $4$, and travels along road $8$. - On day $16$, Little W arrives at city $1$, gains happiness $3$, and ends the trip. - The total happiness gained is $39$. #### Sample 3 See delicacy/delicacy3.in and delicacy/delicacy3.ans in the contestant directory. This sample satisfies $k=0$. --- ### Constraints For all test points: $1 \leq n \leq 50$, $n \leq m \leq 501$, $0 \leq k \leq 200$, $1 \leq t_i \leq T \leq 10^9$. $1 \leq w_i \leq 5$, $1 \leq c_i \leq 52501$, $1 \leq u_i, v_i, x_i \leq n$, $1 \leq y_i \leq 10^9$. The detailed limits for each test point are shown in the table below: | Test Point ID | $n$ | $m$ | $T$ | Special Constraints | | :-: | :-: | :-: | :-: | :-: | | $1\sim 4$ | $\le 5$ | $\le 50$ | $\le 5$ | None | | $5\sim 8$ | $\le 50$ | $\le 50$ | $\le 52501$ | None | | $9\sim 10$ | $\le 50$ | $\le 50$ | $\le 10^9$ | A | | $11\sim 13$ | $\le 50$ | $\le 50$ | $\le 10^9$ | $k=0$ | | $14\sim 15$ | $\le 50$ | $\le 50$ | $\le 10^9$ | $k \le 10$ | | $16\sim 17$ | $\le 50$ | $\le 50$ | $\le 10^9$ | None | | $18\sim 20$ | $\le 50$ | $\le 501$ | $\le 10^9$ | None | Special constraint A: $n = m$ and $u_i = i, v_i = (i \bmod n) + 1$. Translated by ChatGPT 5