Jazz Journey

Ivan is planning a large European tour with his jazz band. There are a total of $n$ cities in Europe, numbered with integers $1$ through $n$. Ivan is planning $d$ concerts in cities $a_1, a_2, \dots , a_ d$ in that exact order, never having two consecutive concerts in the same city ($a_ i \not= a_{i+1}$), possibly visiting some of the cities many times and, finally, ending the tour in the same city where it begun ($a_1 = a_ d$).

Ivan always takes a direct flight between cities $a_ i$ and $a_{i+1}$. However, he is trying to be smart with his ticket purchases in order to save money. As you may know, airlines price tickets based on supply and demand and, for example, it may be possible that one-way tickets are more expensive than round trip tickets between same cities. Generally, there are two kinds of tickets available for purchase:

  • One-way ticket from the origin city $a$ to destination city $b$ can be used to fly from $a$ to $b$ once (but not in the opposite direction).

  • Round trip ticket from the origin city $a$ to destination city $b$ can be used to fly once from $a$ to $b$, and once from $b$ to $a$. The return segment (from $b$ to $a$) does not need to be used. However, the segments have to be flown in order – it is not allowed for Ivan to use the return segment of $a$ ticket to fly from $b$ to a unless he has used the first segment of that ticket to fly from $a$ to $b$ before.

You are given a list of available airfares, find the least amount of money Ivan needs to spend on tickets to be able to complete his journey. Ivan can purchase an arbitrary number of tickets for each airfare. Once again, Ivan needs to take a direct flight from $a_ i$ to $a_{i+1}$ for every $i = 1, 2, \dots , d - 1$. You may assume that is possible to complete the journey using the airfares.


The first line contains two integers $n$ and $d$ ($2 \le n, d \le 300\, 000$) – the number of cities in Europe and the number of concerts. The following line contains integers $a_1, a_2, \dots , a_ d$ ($1 \le ai \le n, ai \not= a_{i+1}, a_1 = a_ d$) – the planned tour schedule.

The following line contains an integer $m$ ($3 \le m \le 300\, 000$) – the number of airfares. The $k$-th of the following $m$ lines contains four tokens $s_ k$, $d_ k$, $t_ k$, $p_ k$, describing the $k$-th airfare as follows:

  • $s_ k$ and $d_ k$ ($1 \le s_ k, d_ k \le n, s_ k \not= d_ k$) are the origin and the destination city respectively,

  • $t_ k$ is an uppercase letter “O” or “R” denoting a one-way or round trip ticket respectively,

  • $p_ k$ ($1 \le pk \le 10^9$) is the ticket price, an integer.


Output the least amount of money necessary to purchase tickets that allow Ivan to complete the planned tour.

Sample Input 1 Sample Output 1
2 5
1 2 1 2 1
1 2 R 6
1 2 O 3
2 1 O 3
1 2 R 5
Sample Input 2 Sample Output 2
4 10
1 2 3 1 2 1 3 2 4 1
2 4 O 10
1 3 R 1
3 1 R 10
2 3 R 20
1 2 R 10
1 2 O 20
2 3 O 5
3 2 O 5
4 1 O 10
CPU Time limit 4 seconds
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in