题目描述

Ivan 正在为他的爵士乐队计划一场规模盛大的欧洲巡演。在欧洲一共有 $n$ 个城市，编号依次为 $1$ 到 $n$。Ivan计划举办 $d$ 场演出，分别在城市 $a_1,a_2,\cdots,a_d$，并且严格遵循这个顺序，而且不会在同一个城市连续巡演两次（即 $a_i\neq a_{i+1}$），但在整个过程中，他可能在一个城市巡演多次。最终，他一定会回到开始的城市进行巡演（即 $a_1=a_d$）。

Ivan 每次总是选择搭乘一趟从 $a_i$ 到 $a_{i+1}$ 的直达航班。然而，他希望变得聪明一些，尽量节省机票的开支。你也知道，机票的价格取决于供给和需求，比如一张单程票可能会比相同目的地的双程票还要贵。一共有两种可以购买的机票：

1. 从 $a$ 到 $b$ 的单程票，每张只能从 $a$ 飞到 $b$ 一次，但不能从 $b$ 飞到 $a$ 。

2. 从 $a$ 到 $b$ 的双程票，只需购买一张，就能从 $a$ 飞到 $b$ 一次，然后从 $b$ 飞回 $a$ 一次，但先从 $b$ 飞回 $a$ 是不允许的。 当然，你也可以选择从 $a$ 飞到 $b$ 之后就再也不返回 $a$。

给定可以购买的机票集合，每种机票都是无限量供应的。请帮助 Ivan 找到一种最省钱的方案。你可以认为合法方案必然存在。

输入格式

第一行包含两个正整数 $n,d$，分别表示城市的个数和巡演的次数。
第二行包含 $d$ 个正整数 $a_1,a_2,\cdots,a_d$，依次表示巡演计划中每一场所在的城市。
接下来一行包含一个正整数 $m$，表示机票的种类数。
接下来 $m$ 行，每行首先是两个正整数 $s_i,d_i$，分别表示起点与终点；接下来一个字符 $t_i$，表示机票的类型，其中 O 表示单程票，R 表示双程票；最后是一个正整数 $p_i$，表示票价。

输出格式

输出一行一个整数，即完成巡演所需支付的最小机票总费用。

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

数据规模与约定

对于 $100\%$ 的数据，$2\le n,d\le 3\times 10^5$，$1\le a_i\le n$，$a_1=a_d$，$a_i\neq a_{i+1}$，$3\le m\le 3\times 10^5$，$1\le s_i,d_i\le n$，$s_i\neq d_i$，$1\le p_i\le 10^9$。