- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
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$, describing the number of pistons and the length of cylinders, respectively. Each of the next $n$ lines describe the position and direction of a single piston. The $(i + 1)^{th}$ line of the input contains an integer $p_i$ and a character $d_i$ , the initial position of the $i^{th}$ piston and its direction (Up or Down), respectively.
$$1 \leq n \leq 10^5$$ $$1 \leq m \leq 10^6$$ $$0 \leq p_i \leq m$$ $$d_i \in { U, D }$$
خروجی
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
ارسال پاسخ برای این سؤال