deathray

Problem Statement

The nefarious Physicist S has constructed a death ray! Being the evil mastermind he is, he has gathered N willing volunteers to test the death ray.

The N volunteers stand in a line, each of them having life L_i.

Physicist S will perform Q actions. There are two actions he can perform:

• hit all N volunteers with the death ray at power P_i, making each of them lose P_i life. If a volunteer has no life remaining, he faints.
• give the conscious (i.e. not fainted) volunteer with the least life a drink which restores D_i life. If all volunteers are unconscious, this operation has no effect. If multiple volunteers have the same amount of life, it is effective on any one of them (it can be shown that this does not affect final result).

His supervisor, H, is trying to determine the number of volunteers they have to send to the hospital after the experiment (i.e. the number of volunteers who will faint during the course of the experiment). Code a program to help her!

Input

The first line of input contains two integers, N and Q.

The next line of input contains N integers, representing the array L.

The next Q lines of input indicate Physicist S's actions. They contain a character C_i and an integer as follows:

• C_i = 'A' will be followed by an integer P_i. This indicates an attack operation with the death ray at power P_i.
• C_i = 'B' will be followed by an integer D_i. This indicates a healing operation which restores D_i life to the conscious volunteer with least life, if such a volunteer exists.

Output

The first and only line of output should contain a single integer, denoting the number of volunteers who faint during the experiment.

Limits

For all subtasks, 1 ≤ N, Q ≤ 100000 and 1 ≤ L_i, P_i, D_i ≤ 10⁹. C_i will be either 'A' or 'B'.

Subtask 1 (30%): N, Q ≤ 1000

Subtask 2 (10%): C_i = 'A' for all updates.

Subtask 3 (20%): Physicist S fires his death ray at most 10 times.

Subtask 4 (40%): No additional constraints.

Subtask 5 (0%): Sample test cases.

Sample Input

5 7
1 2 3 4 5
A 1
B 3
A 2
B 2
A 2
B 3
A 1

Sample Output

4

Explanation

Health after each operation is indicated below. Bold indicates the person healed on a type B operation. A person with 0 health has fainted.

1. 0 1 2 3 4
2. 0 4 2 3 4
3. 0 2 0 1 2
4. 0 2 0 3 2
5. 0 0 0 1 0
6. 0 0 0 4 0
7. 0 0 0 3 0