시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 36 | 21 | 20 | 60.606% |
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 a1, a2, . . . , ad in that exact order, never having two consecutive concerts in the same city (ai ≠ ai+1 ), possibly visiting some of the cities many times and, finally, ending the tour in the same city where it begun (a1 = ad ).
Ivan always takes a direct flight between cities ai and ai+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:
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 ai to ai+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 a1, a2, . . . , ad (1 ≤ ai ≤ n, ai ≠ ai+1 , a1 = ad ) — 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 sk , dk , tk , pk , describing the k-th airfare as follows:
Output the least amount of money necessary to purchase tickets that allow Ivan to complete the planned tour.
2 5 1 2 1 2 1 4 1 2 R 6 1 2 O 3 2 1 O 3 1 2 R 5
10
4 10 1 2 3 1 2 1 3 2 4 1 9 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
60