25071번 - Delicacy 다국어

There are $n$ cities numbered from $1$ to $n$. The delicacy at city $i$ may provide $c_i$ units of happiness. The cities are connected by $m$ one-directional roads, and the roads are numbered from $1$ to $m$. Road $i$ begins in city $u_i$ and ends in city $v_i$. It takes $w_i$ days to travel along road $i$. In other words, if one departs from city $u_i$ and travels along road $i$ on day $d$, then the person will arrive at city $v_i$ on day $d + w_i$.

W is planning a trip lasting $T$ days. More specifically, he will depart from city $1$ on day $0$, travel $T$ days, and return to city $1$ on day $T$ exactly and finish the trip. Since W is an epicure, once W arrives in a city (including city $1$ on day $0$ and day $T$), he will try the delicacies in that city and gain some units of happiness. If W visits a city multiple times, he is able to gain the units of happiness multiple times. Notice that W may not stop at any city, which means if he arrives in a city and the trip hasn't ended, he must depart the city on the same day.

For the above example, a possible itinerary lasting $11$ days for W is $1 \to 2 \to 1 \to 2 \to 3 \to 1$. The total units of happiness of the trip is $13$.

Moreover, there are $k$ food festivals happening at different times. More formally, the $i$-th food festival is hosted in city $x_i$ on day $t_i$. If W is in city $x_i$ on $t_i$-th day, then he will obtain an additional $y_i$ units of happiness for tasting the delicacies in city $x_i$. Now W wants to know the maximum possible units of happiness he may get from the trip.

The input begins with four integers $n,m,T,K$, denoting the number of cities, the number of roads, the length of the trip, and the number of food festivals. The second line contains $n$ integers $c_i$ denoting the units of happiness W may obtain from tasting the delicacies in each city. The following $m$ lines contain three integers $u_i,v_i,w_i$ each denoting the start, end, and the days required to travel along road $i$. The last $k$ lines contain three integers $t_i,x_i,y_i$ on each line, denoting the time of the food festival, the host city, and the additional units of happiness the food festival can provide.

The data guarantees: for all $i$, we have $u_i \ne v_i$. However, there might be parallel one-directional roads, or in other words, there may exist $1 \le i < j \le m$ such that $u_i = u_j$ and $v_i = v_j$. For each city, there exists a road departing the city. The time of the food festivals $t_i$ are distinct.

The output contains only one integer, denoting the maximum possible level of happiness W may obtain from the trip. If W cannot return to city $1$ on day $T$, output -1.

For all test cases, $1 \le n \le 50$, $n \le m \le 501$, $0 \le k \le 200$, $1 \le t_i \le T \le 10^9$. $1 \le w_i \le 5$, $1 \le c_i \le 52501$, $1 \le u_i, v_i, x_i \le n$, $1 \le y_i \le 10^9$