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.

Input Specification

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.

Output Specification

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.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

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

Sample Output 2

39

The optimal itinerary is ~1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1~.

Constraints

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 52\,501~, ~1 \le u_i, v_i, x_i \le n~, ~1 \le y_i \le 10^9~.

Test Case	~n~	~m~	~T~	Additional Constraints
1~4	~\le 5~	~\le 50~	~\le 5~	None.
5~8	~\le 50~		~\le 52\,501~
9~10			~\le 10^9~	~n = m~ and ~u_i = i~, ~v_i = (i \bmod n) + 1~.
11~13				~k = 0~
14~15				~k \le 10~
16~17				None.
18~20		~\le 501~