Maximum Enjoyment Tour

ID: 19979

Type: Default

1000ms

256MiB

The Maximum Enjoyment Tour problem is set in the elven kingdom of the Bzeroth continent. After repelling the invasion of the "Disaster Legion," the kingdom has blossomed again and now attracts tourists from all over. The famous gourmet traveler, W, visits the kingdom to enjoy its culinary delights.

The kingdom has \(n\) cities numbered from \(1\) to \(n\). When arriving at city \(i\), W obtains an enjoyment value of \(c_i\). The cities are connected by \(m\) directed roads. The \(i\)th road goes from city \(u_i\) to city \(v_i\) and takes \(w_i\) days to travel (i.e. if starting on day \(d\) from \(u_i\), you will arrive at \(v_i\) on day \(d+w_i\)).

W plans a trip lasting exactly \(T\) days. He starts at city \(1\) on day 0 and must return to city \(1\) exactly on day \(T\). Whenever he arrives at a city (including the starting city on day 0 and the ending city on day \(T\)), he immediately enjoys the city’s cuisine and gains its enjoyment value; if he visits the same city multiple times, he gains its enjoyment each time. Note that during the journey, W cannot wait or stay in any city – once he arrives at a city (unless it is the final day), he must depart immediately.

In addition, the elven kingdom hosts a series of \(k\) food festivals at different times. The \(i\)th festival is held on day \(t_i\) in city \(x_i\), and if W happens to be in city \(x_i\) on day \(t_i\), he gets an extra enjoyment value of \(y_i\) (in addition to the city’s usual enjoyment value).

Your task is to help W determine the maximum total enjoyment he can achieve during his trip.

Input Format

The input begins with four integers: \(n\), \(m\), \(T\) and \(k\) \ (\(1 \le n \le \text{?}\), \(1 \le m \le \text{?}\), \(T \ge 0\), \(k \ge 0\)).

The next line contains \(n\) integers \(c_1, c_2, \ldots, c_n\) where \(c_i\) is the enjoyment value of city \(i\).

Then \(m\) lines follow, each containing three integers \(u_i\), \(v_i\) and \(w_i\) representing a directed road from city \(u_i\) to city \(v_i\) that takes \(w_i\) days.

Finally, \(k\) lines follow, each containing three integers \(t_i\), \(x_i\) and \(y_i\) indicating that on day \(t_i\) there is a food festival in city \(x_i\) which provides an extra enjoyment value of \(y_i\) if W is in city \(x_i\) on that day.

Output Format

Output a single integer: the maximum total enjoyment value W can collect on a valid travel route that starts at city \(1\) on day 0 and returns to city \(1\) exactly on day \(T\). It is guaranteed that at least one valid route exists.

Example

Input (Test Case 1):

Explanation: One possible route is: 1 \(\to\) 2 \(\to\) 1 \(\to\) 2 \(\to\) 3 \(\to\) 1 with arrival days 0, 1, 4, 5, 7, and 11 respectively. The enjoyment values collected are:

Day 0 at city 1: \(1\)
Day 1 at city 2: \(3\)
Day 4 at city 1: \(1\)
Day 5 at city 2: \(3\)
Day 7 at city 3: \(4 + 10 \; (festival)\)
Day 11 at city 1: \(1\)

Total = \(1+3+1+3+14+1 = 23\).

inputFormat

The first line contains four integers \(n\), \(m\), \(T\), and \(k\).
The second line contains \(n\) integers representing \(c_1, c_2, \ldots, c_n\).
Then \(m\) lines follow, each with three integers \(u_i\), \(v_i\), and \(w_i\), describing a directed road.
Finally, \(k\) lines follow, each with three integers \(t_i\), \(x_i\), and \(y_i\), describing a food festival.

Note: If \(k=0\), then no festival lines will be provided.

outputFormat

Output one integer indicating the maximum total enjoyment value achievable on a trip starting and ending at city 1 at the specified times.

sample

#P6772. Maximum Enjoyment Tour

Maximum Enjoyment Tour