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 Li.

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

  • hit all N volunteers with the death ray at power Pi, making each of them lose Pi 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 Di 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!


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 Ci and an integer as follows:

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


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


For all subtasks, 1 ≤ N, Q ≤ 100000 and 1 ≤ Li, Pi, Di ≤ 109. Ci will be either 'A' or 'B'.

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

Subtask 2 (10%): Ci = '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



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

Submitting .cpp to 'deathray'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Dec Trg 2019 (Elementary) (shenxy13)

Subtask Score
1 30
2 10
3 20
4 40
5 0