13954번 - 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₁, a₂, . . . , a_d in that exact order, never having two consecutive concerts in the same city (a_i ≠ a_i+1 ), possibly visiting some of the cities many times and, finally, ending the tour in the same city where it begun (a₁ = 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, . . . , 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 ≤ n, d ≤ 300 000) — the number of cities in Europe and the number of concerts. The following line contains integers a₁, a₂, . . . , a_d (1 ≤ a_i ≤ n, a_i ≠ a_i+1 , a₁ = a_d ) — the planned tour schedule.

The following line contains an integer m (3 ≤ m ≤ 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 ≤ s_k , d_k ≤ n, s_k ≠ 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,
• k (1 ≤ p_k ≤ 10⁹ ) is the ticket price, an integer.

출력

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

제한

힌트