Concert Tour Ticket Cost

David, an enthusiastic concert fan, is planning a tour across several cities to attend concerts in a specified order. The cities are numbered from 1 to n, and the sequence of concerts is given as an ordered list of cities. David can choose from different train tickets that connect pairs of cities. There are two types of tickets:

• One-way (O): a ticket from city u to city v with a given cost.
• Round-trip (R): a ticket that can be used in either direction (from u to v and from v to u) with the stated cost.

Your task is to help David determine the minimal total cost to travel along the concert route. Between two consecutive concerts, he may have to take one or more tickets; however, the available tickets directly connect some cities at a certain cost. In each leg of his journey (from one concert city to the next), determine the cheapest way to get from the starting city to the destination using the available ticket fares. The overall minimal cost is the sum for all the legs of the tour.

The solution involves modeling the journey as a graph and using Dijkstra’s algorithm to find the shortest path between cities.

Note: All formulas are in LaTeX. For example, the cost computed for each leg is given by \( \min_{paths} \sum_{edge \in path} cost(edge) \).

inputFormat

The input is read from standard input (stdin) and has the following format:

 n d
 c1 c2 ... cd
 m
 u1 v1 w1 q1
 u2 v2 w2 q2
 ...
 um vm wm qm

Where:

• \(n\) is the total number of cities.
• \(d\) is the number of concerts, followed by \(d\) integers representing the city numbers (1-indexed) where the concerts are held in order.
• \(m\) is the number of train ticket fares available.
• Each of the next \(m\) lines contains four entries: \(u\) and \(v\) (the cities the ticket connects), a character \(w\) representing the ticket type (\(O\) for one-way or \(R\) for round-trip), and \(q\), the ticket price.

outputFormat

Output a single integer to the standard output (stdout): the minimum total amount of money needed for David to complete his concert tour.

## sample

3 4
1 2 3 1
5
1 2 O 7
2 3 O 5
3 1 O 8
2 3 R 9
1 2 R 12

20