Problem Description

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.

Input Format

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 Format

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

3 4 11 0
1 3 4
1 2 1
2 1 3
2 3 2
3 1 4

13

4 8 16 3
3 1 2 4
1 2 1
1 3 1
1 3 2
3 4 3
2 3 2
3 2 1
4 2 1
4 1 5
3 3 5
1 2 5
5 4 20

39

Hint

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:

Special constraint A: $n = m$ and $u_i = i, v_i = (i \bmod n) + 1$.

Translated by ChatGPT 5