D. Traffic Lights
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As a respectful and punctual boyfriend, you have to be on time for your dinner reservation. However, you are also a good citizen and respect traffic lights, or else you'll get a fine and you'll have no money left for food :(

In an $$$[Ox)$$$ plan with the restaurant $$$X$$$ meters away and you being at position $$$0$$$, you encounter $$$n$$$ traffic lights denoted by the triplets $$$c$$$ $$$p$$$ $$$t$$$:

  • $$$c$$$: character, indicating the signal color, either 'R' (red) or 'G' (green).
  • $$$p$$$: integer, position of the traffic light along the road.
  • $$$t$$$: integer, time duration for each state switch.

Assuming you walk at a speed of $$$1$$$ $$$meter/second$$$, determine the time it takes in seconds to reach the restaurant.

Input

The first line contains two integer $$$n$$$ and $$$X$$$, the number of traffic lights, and the distance in meters of the restaurant. $$$(1\leq n \lt X\leq 10^{5})$$$

The next $$$n$$$ lines each have $$$c$$$ $$$p$$$ $$$t$$$ $$$(1 \leq p \lt X, 1 \leq t \lt 100, c=\text{'G'}$$$ or $$$c=\text{'R'})$$$

Output

Print the time in seconds to reach the restaurant, while respecting all the traffic lights.

Example
Input
3 100
R 5 10
R 10 50
G 50 70
Output
190
Note

Note 1 : If $$$c$$$ is 'R' and $$$t$$$ is 5, it implies that from $$$[0,5[$$$ seconds, the signal is red; from $$$[5,10[$$$, it's green; $$$[10,15[$$$, red, and so on...

Note 2: All of the traffic lights' positions are distinct.