题目描述

Maryam, a famous mathematician, recently has bought an old vintage car. This car uses a combustion engine to generate the power needed to move the car. Inside the engine, there are $n$ cylinders of length $m$ and inside each cylinder, there is a piston constantly moving up and down. All pistons move independently and at the same speed. At any given time, the position of a piston inside a cylinder can be shown with an integer from 0 to $m$, which also describes the area of the cylinder occupied by the piston. A piston instantly changes its direction when it reaches the top (position $m$) or bottom (position 0) of its cylinder.

Maryam managed to determine the position and direction of all the pistons at a specific time. Now she is curious about the maximum total area occupied by all the pistons. Help Maryam find out this value.

输入格式

The first line of input contains two integers $n$ and $m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 10^6$), describing the number of pistons and the length of cylinders, respectively. Each of the next $n$ lines describe $p_i$ ($0 \leq p_i \leq m$), and a character $d_i$ ($d_i \in \{U, D\}$), the initial position of the $i^{th}$ piston and its direction (Up or Down), respectively.

输出格式

Print a single integer, the maximum total area occupied by all the pistons.

2 5
2 U
5 D

7

4 6
0 U
0 D
6 U
3 U

15