피스톤

시간 제한1초메모리 제한2048 MB

요약

길이 m인 실린더 n개에서 위치와 방향이 주어진 피스톤들이 움직일 때, 앞으로 가능한 시점 중 피스톤 면적의 합이 최대가 되는 값을 구합니다.

난이도: 보통10점 중 6점
유형: 배열, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

Maryam은 유명한 수학자로, 최근 오래된 빈티지 자동차를 한 대 샀다. 이 차는 내연기관으로 차를 움직이는 데 필요한 동력을 만든다. 엔진 안에는 길이가 $m$ 인 실린더가 $n$ 개 있고, 각 실린더 안에서 피스톤 하나가 위아래로 계속 움직인다. 모든 피스톤은 서로 독립적으로, 같은 속력으로 움직인다. 어떤 순간이든 실린더 안 피스톤의 위치는 $0$ 부터 $m$ 까지의 정수로 나타내며, 이 값은 피스톤이 차지하는 실린더의 면적과 같다. 피스톤은 실린더의 위쪽 끝( $m$ )이나 아래쪽 끝( $0$ )에 닿으면 곧바로 방향을 바꾼다.

Maryam은 특정한 한 순간에 모든 피스톤의 위치와 방향을 알아냈다. 모든 피스톤이 차지하는 면적의 합이 가질 수 있는 최댓값을 구하라.

입력

첫 줄에 피스톤의 개수 $n$ 과 실린더의 길이 $m$ 이 공백으로 구분된 두 정수로 주어진다 ( $1 \le n \le 10^5$ , $1 \le m \le 10^6$ ). 이어지는 $n$ 개의 줄에는 $i$ 번째 피스톤의 초기 위치 $p_i$ ( $0 \le p_i \le m$ )와 방향 $d_i$ 가 주어진다. $d_i$ 는 U(위) 또는 D(아래)이다.

출력

모든 피스톤이 차지하는 면적 합의 최댓값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
2 5
2 U
5 D
```
예상 출력
```
7
```
예제 2
입력
```
4 6
0 U
0 D
6 U
3 U
```
예상 출력
```
15
```