I. Inside the Guinea Pig Playpen
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jaime, a friendly guinea pig, and their clever friend Churro, also a guinea pig, have won the International Cavy Programming Contest. To celebrate their victory, they are organizing a party. They have $$$F$$$ other friends, numbered from $$$1$$$ to $$$F$$$, and sent invitations to $$$N$$$ of them (due to some budget limitations). Each invitation may cover several guests, such as the invited friend's family.

Each invited friend either accepted the invitation and specified their group's schedule, declined the invitation, or gave a tentative response that depends on whether another friend attends.

If a tentative response depends on a friend who declined, on a friend who was not invited, or on a circular chain of tentative responses, that friend will not attend.

Jaime and Churro will prepare a party playpen for the invited groups. At the minute when a group leaves, it no longer occupies the playpen, so its space can be used by groups arriving at that same minute. Determine the minimum guest capacity required for the playpen to accommodate all attending groups, excluding Jaime and Churro.

Input

The first line contains two integers $$$F$$$ and $$$N$$$ ($$$1 \leq F \leq 10^{9}$$$, $$$1 \leq N \leq \min(10^{5}, F)$$$), the total number of their friends and the number of invitations, respectively.

Each of the next $$$N$$$ lines contains two integers $$$k_i$$$ and $$$p_i$$$ ($$$1 \leq k_i \leq F$$$, $$$1 \leq p_i \leq 10^{5}$$$). These values indicate that the $$$i$$$-th invitation was sent to friend $$$k_i$$$ and covers a group of exactly $$$p_i$$$ guests, including friend $$$k_i$$$. All values $$$k_i$$$ are distinct.

Each of the next $$$N$$$ lines contains the response to the corresponding invitation, in the same order as the invitations. A response has one of the following forms:

  • A $$$a_i$$$ $$$t_i$$$ ($$$1 \leq a_i \leq 10^{9}$$$, $$$1 \leq t_i \leq 10^{9}$$$): friend $$$k_i$$$ accepted; their group will arrive at minute $$$a_i$$$, stay for $$$t_i$$$ minutes, and leave at minute $$$a_i + t_i$$$.
  • D: friend $$$k_i$$$ declined.
  • T $$$x_i$$$ ($$$1 \leq x_i \leq F$$$): friend $$$k_i$$$ will attend if and only if friend $$$x_i$$$ attends; in that case, both groups will arrive and leave at the same times.
Output

Print one integer: the minimum guest capacity required for the party playpen.

Example
Input
10 5
1 1
2 2
3 3
7 1
9 1
A 1 3
D
T 2
T 1
T 7
Output
3
Note

Explanation for example 1

Friend $$$1$$$ accepted the invitation, which covers only that friend. Friend $$$2$$$ declined, so friend $$$3$$$, whose response depends on friend $$$2$$$, does not attend.

Friend $$$7$$$ depends on friend $$$1$$$, and friend $$$9$$$ depends on friend $$$7$$$. Therefore, friends $$$1$$$, $$$7$$$, and $$$9$$$ all attend from minute $$$1$$$ to minute $$$4$$$. Their invitations cover $$$1$$$ guest each, so the maximum number of guests in the playpen at the same time is $$$3$$$.