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.