After the Elven Kingdom on the continent of Bzeroth repelled the invasion of the Scourge, it has spent over a decade recuperating and has once again become a prosperous land, attracting tourists from all directions. Little W, a famous gourmet who has traveled all over the world, has now come to the Elven Kingdom out of admiration.

The Elven Kingdom has $n$ cities, numbered from 1 to $n$. The food in city $i$ provides Little W with a pleasure value of $c_i$. The cities in the Elven Kingdom are connected by $m$ one-way roads, numbered from 1 to $m$. Road $i$ starts at city $u_i$ and ends at city $v_i$, and it takes $w_i$ days to travel along it. That is to say, if Little W travels along road $i$ from city $u_i$ on day $d$, he will arrive at city $v_i$ on day $d + w_i$.

Little W plans to take a trip in the Elven Kingdom for $T$ days. Specifically, he will start from city 1 on day 0, travel for $T$ days, and finally return to city 1 exactly on day $T$ to end his trip. Since Little W is a gourmet, every time he arrives at a city (including the city on day 0 and day $T$), he will taste the food in that city and receive the pleasure value it provides. If Little W arrives at the same city multiple times, he will receive the pleasure value multiple times. Note that during the trip, Little W cannot stay in any city; that is, when he arrives at a city and has not yet finished his trip, he must immediately depart from that city on the same day to head to another city.

In addition, the Elven 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 happens to be in city $x_i$ on day $t_i$, he will receive an additional pleasure value of $y_i$ when tasting the food in city $x_i$. Now, as the reception envoy of the Elven Kingdom, you are asked to help him calculate the maximum total pleasure value he can obtain during his trip.

Input

Read the data from the file delicacy.in.

The first line contains four integers $n, m, T, k$, representing the number of cities, the number of roads, the number of days of the trip, and the number of food festivals, respectively.

The second line contains $n$ integers $c_i$, representing the pleasure value provided by the food in each city.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, representing the starting city, ending city, and travel time for each road, respectively.

The last $k$ lines each contain three integers $t_i, x_i, y_i$, representing the time, city, and additional pleasure value for each food festival, respectively.

Data in this problem guarantees: For all $1 \le i \le m$, $u_i \neq v_i$. However, there may be duplicate one-way roads in the data, i.e., there may exist $1 \le i < j \le m$ such that $u_i = u_j$ and $v_i = v_j$. For every city, there is at least one one-way road starting from that city. * The times $t_i$ of all food festivals are distinct.

Output

Output to the file delicacy.out.

Output a single integer representing the maximum total pleasure value Little W can obtain during his trip.

If Little W cannot return to city 1 on day $T$, output -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$.

The specific constraints for each test case are shown in the table below:

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

Examples

Input 1

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

Output 1

13

Note 1

This example is the one described in the problem statement; see the description for the optimal travel plan.

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

Output 2

39

Note 2

The optimal plan is $1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1$. Day 0: Little W starts from city 1, receives pleasure value 3, and travels along road 3. Day 2: Little W arrives at city 3, receives pleasure value 2, and travels along road 4. Day 5: Little W arrives at city 4, receives pleasure value $20 + 4$ due to the food festival, and travels along road 7. Day 6: Little W arrives at city 2, receives pleasure value 1, and travels along road 5. Day 8: Little W arrives at city 3, receives pleasure value 2, and travels along road 4. Day 11: Little W arrives at city 4, receives pleasure value 4, and travels along road 8. Day 16: Little W arrives at city 1, receives pleasure value 3, and ends the trip. The total pleasure value obtained by Little W is 39.

Input 3

See delicacy/delicacy3.in and delicacy/delicacy3.ans in the contestant directory. This example satisfies $k = 0$.

Figure 1. The city network and pleasure values for the example problem.