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 52501$, $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 52501$
9~10			$\le {10}^9$	$n=m$ and $u_i=i$, $v_i=(imodn)+1$.
11~13				$k=0$
14~15				$k\le 10$
16~17				None.
18~20		$\le 501$