Jazz Band European Tour Ticket Optimization

Ivan is planning a grand European tour with his jazz band. In Europe there are \(n\) cities numbered from \(1\) to \(n\). He will hold \(d\) concerts in the cities \(a_1, a_2, ..., a_d\) in that exact order. It is guaranteed that \(a_1 = a_d\) and no two consecutive concerts take place in the same city (i.e. \(a_i \neq a_{i+1}\) for all valid \(i\)), although a city may appear several times in the tour.

For every leg of his journey, Ivan must take a direct flight from city \(a_i\) to \(a_{i+1}\) (for \(1 \le i < d\)). Ticket prices, however, depend on supply and demand so that sometimes a one‐way flight might be more expensive than a round‐trip flight. There are two types of tickets available:

1. One-way ticket: A ticket from city \(a\) to city \(b\) that allows you to fly from \(a\) to \(b\) exactly once. It cannot be used in the reverse direction.
2. Round-trip ticket: A ticket from city \(a\) to city \(b\) which, after buying just one ticket, allows you to first fly from \(a\) to \(b\) and later from \(b\) back to \(a\). Note that you must use the \(a \to b\) flight before using the \(b \to a\) flight. Moreover, if you choose, you may use the ticket only for the first leg (i.e. fly from \(a\) to \(b\) and never use the return flight).

There is an unlimited supply for each available ticket option. Given a list of available tickets, please help Ivan choose a set of tickets so that he can cover every flight of his tour at minimum total cost. A valid purchase plan exists for every input instance.

Hint (Dynamic Programming): Let the tour contain \(N = d-1\) flight segments. For each segment from city \(u\) to \(v\), you can buy a ticket independently at cost \(c_{ind}(u,v)=\min\{\text{one-way cost}(u,v),\,\text{round-trip cost}(u,v)\}\). Alternatively, if there exists a later flight segment from \(v\) to \(u\) (with \(i < j\)) and a round-trip ticket from \(u\) to \(v\) is available, you can cover both flights with a single round-trip ticket costing \(c_{rt}(u,v)\) instead of paying \(c_{ind}(u,v)+c_{ind}(v,u)\). One can use dynamic programming with precomputed cumulative independent costs to decide whether to pair two segments.

inputFormat

The first line contains three integers \(n, d, m\) where \(n\) is the number of cities, \(d\) is the number of concerts, and \(m\) is the number of available ticket options.

The second line contains \(d\) integers \(a_1, a_2, \dots, a_d\) representing the sequence of cities in the tour. It is guaranteed that \(a_1 = a_d\) and \(a_i \neq a_{i+1}\) for \(1 \le i < d\).

Each of the next \(m\) lines contains four space‐separated values: an integer type (either 1 or 2), and three integers a, b and cost. Here, type = 1 indicates a one‑way ticket from city a to city b, and type = 2 indicates a round‑trip ticket from city a to city b (which can be used for both the \(a \to b\) flight and the \(b \to a\) flight, if used in order).

outputFormat

Output a single integer — the minimum total cost required to cover all the flight segments in the tour.

sample

3 4 4
1 2 3 1
1 1 2 100
1 2 3 100
1 3 1 100
2 1 2 150

300