## NOI '20 P1 - Delicacy

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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

W is planning a trip lasting days. More specifically, he will depart from city on day , travel days, and return to city on day exactly and finish the trip. Since W is an epicure, once W arrives in a city (including city on day and day ), 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 days for W is . The total units of happiness of the trip is .

Moreover, there are food festivals happening at different times. More formally, the -th food festival is hosted in city on day . If W is in city on -th day, then he will obtain an additional units of happiness for tasting the delicacies in city . 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 , denoting the number of cities, the number of roads, the length of the trip, and the number of food festivals. The second line contains integers denoting the units of happiness W may obtain from tasting the delicacies in each city. The following lines contain three integers each denoting the start, end, and the days required to travel along road . The last lines contain three integers 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 , we have . However, there might be parallel one-directional roads, or in other words, there may exist such that and . For each city, there exists a road departing the city. The time of the food festivals 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 on day , 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 .

#### Constraints

For all test cases, , , , .
, , , .

1~4None.
5~8
9~10 and , .
11~13
14~15
16~17None.
18~20