Santa has visited, and you have found a new video game under your Christmas tree!

In this video game, the player attempts to collect stars scattered around the game world. After collecting a single star, they return to the starting location until all stars have been collected. Moving around requires various manipulating various buttons on the controller, including the A button. What is the minimum number of times the A button must be pressed in order to collect all the stars and beat the game?

The game world consists of $N$ locations numbered from $1$ to $N$. There are $s_i$ stars at location $i$. Location $1$ is the starting location where the player starts the game, and is returned to after collecting a star. There are $M$ known techniques for going from one location to another, these are numbered from $1$ to $M$. The $i^{\text{th}}$ of these techniques is for going from location $a_i$ to location $b_i$. These techniques each have different requirements regarding the A button that will be specified in more detail later.

The A button has two states: pressed, and unpressed. Initially, the button is unpressed. Going from the unpressed state to the pressed state is called "pressing the A button". The number of these A presses is the quantity we want to minimize. Note that once the A button is pressed, it does not need to be released right away. The A button can continue to be held even while collecting a star and returning to the starting location.

Each technique has a type $t_i$ which is either A, B, or C.

• Type A techniques require performing an additional $x_i$ A presses.
• Type B techniques require performing an additional $x_i$ A presses under the condition that the A button is already being held (in real-life applications, this extra requirement is known as a "half" A press).
• Type C techniques simply require the A button to be in the unpressed state.

Note that the A button can be manipulated even outside of these techniques - while at one of the $N$ locations the button can be pressed or released at any time.

Constraints

$1\le N,M\le {10}^5$

$0\le s_i\le {10}^5$

$1\le a_i,b_i\le N$

$t_i$ is either A, B, or C.

$0\le x_i\le 100$

It is guaranteed that it is possible to collect all the stars.

Subtask 1 [50%]

There are no type C techniques.

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains two space-separated integers $N$ and $M$.

The next line contains $N$ space-separated integers $s_i$.

The next $M$ lines first contain $a_i$, $b_i$, and $t_i$. If $t_i$ is A or B, then the line also contains $x_i$.

Output Specification

Output a single integer, the minimum number of A presses needed for collecting all stars.

Sample Input

3 3
0 0 5
1 2 B 0
2 3 C
1 3 A 1

Output for Sample Input

3

Explanation for Sample Output

First, press the A button to travel from 1 to 3 and keep it down. After collecting a star, you are returned to 1 with the A button down. The B technique can then be used to travel to 2. Letting go of the A button allows the C technique, which moves you to 3 and after collecting a second star, back to 1. Repeating this process twice lets you go to 3 enough times to collect all the stars. In total, 3 button presses are made.