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$

힌트