G. AB Factory
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In AB Factory, two products are manufactured, namely product A and product B. The factory could produce $$$1$$$ unit of product A or $$$1$$$ unit of product B each day. Ian is the director of the factory. He can decide when to change the product to manufacture. To check if the factory is working properly, Ian's boss would come and check if there are enough stocks of some products. Formally speaking, his boss comes to check $$$N$$$ times, the $$$i$$$-th check happens at time $$$t_i$$$, checking if there are at least $$$x_i$$$ units of product $$$p_i$$$. If there are enough desired products, Ian's boss would be happy and gives Ian $$$v_i$$$ dollars as a bonus.

Ian wonders how much money he could make if he plans the manufacturing product optimally. Help him calculate the answer.

Input

The first line consists of one integer $$$N$$$, representing the number of times Ian's boss comes.

Each of the following $$$N$$$ lines consists of three integers $$$t_i$$$, $$$x_i$$$, $$$v_i$$$ and a character $$$p_i$$$, representing the time, the desired amount, the amount of the bonus for the $$$i$$$-th check, and the type of the desired product.

  • $$$1 \leq N \leq 10^{5}$$$
  • $$$1 \leq t_i, x_i, v_i \leq 10^{9}$$$
  • $$$t_i \not= t_j$$$ for $$$i \neq j$$$
  • $$$p_i$$$ is either A or B
Output

Output a single line with the answer to Ian's question.

Examples
Input
3
8 4 4 A
7 4 3 B
3 2 5 B
Output
12
Input
3
5 4 4 B
8 5 1 A
10 9 1 A
Output
4