Sunsprint

The sun is back at it again trying to burn you. You are in a park with $N$ shaded rest stops (numbered $0$ to $N-1$). Between them are $M$ one-way paths which may either be shaded or open to the sun. The paths are laid out in such a way that it is not possible to get back to a rest stop after leaving it. You need to get from rest stop $0$ to rest stop $N-1$, and want to minimise your risk of getting sunburnt. You are guaranteed that it is possible to get from rest stop $0$ to rest stop $N-1$.

Luckily there are a few clouds about to cover the sun, and you also happen to have been blessed with perfect knowledge of the weather by a druid. Therefore you know exactly how intense the sunlight is going to be in the park for each second of the cloud cover. Intensity may range from $0$ to $I$. After the cloud cover is over (after $T$ seconds) the intensity will be $I$ indefinitely.

During each second, you must either wait at a rest stop (if you are at one), or walk along a path. Each path takes an integer number of seconds to travel along. For each second you travel on a path that is open to the sun, you accumulate exposure equal to the intensity of the sun at that second.

Minimise your total sunlight exposure (the sum of all intensities you are exposed to).

Input

The first line contains 2 space-separated integers, $I$ and $T$.

The second line contains $T$ space separated integers $s_1, s_2, \ldots, s_T$, the sunlight intensities for each second.

The third line contains 2 space separated integers, $N$ and $M$.

The remaining $M$ lines each contain three space-separated integers $a$, $b$, $d$, followed by a character ('S' or 'O'), indicating a path from rest stop $a$ to rest stop $b$ that takes $d$ seconds to travel along. 'S' indicates the path is shaded while 'O' indicates the path is open to the sun.

Output

A single integer, the minimum total exposure possible while getting from rest stop $0$ to rest stop $N-1$.

Constraints

• $0 \leq I \leq 1000$
• $0 \leq T \leq 5000$
• $0 \leq s_i \leq I$ for all i
• $1 \leq N \leq 2000$
• $0 \leq M \leq 5000$
• $0 \leq a,b \leq N-1$
• $0 \leq d \leq 500$

Subtasks

• Subtask 1 (+10%): $T=0$, $N \leq 20$, $M \leq N(N-1)/2$
• Subtask 2 (+15%): $T=0$
• Subtask 3 (+10%): $d \leq 1$
• Subtask 4 (+20%): $M=N-1$, $b=a+1$ for all paths (i.e. the paths form a line), and $d \leq 3$ for all paths.
• Subtask 5 (+20%): $d \leq 3$ for all paths.
• Subtask 6 (+25%): No further constraints.

NOTE

If you are using Python, select Python 3.6 (PyPy 7.3) when submitting. Otherwise, your solution may not pass the time limit even if it is maximally efficient.