빨강 검정 공

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

요약

열린 색 공을 넣는 순서 중 최종적으로 빨간 공이 검은 공보다 많아지는 순서의 수를 998244353으로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 정렬
정답자: 아직 제출이 없습니다

문제

색이 바뀌는 공이 $N + M$ 개 있으며, 각 공의 번호는 0 이상 $10^9$ 이하의 서로 다른 정수다. 이 중 $N$ 개는 빨강 또는 검정으로 색이 고정된 공(유색 공)이고, 나머지 $M$ 개는 색이 정해지지 않은 공(무색 공)이다. 무색 공은 유색 공이 하나 이상 들어 있는 컨테이너에 넣으면 색이 정해진다. 무색 공은 번호 차이의 절댓값이 가장 작은 유색 공과 같은 색이 된다. 차이가 같은 유색 공이 두 개면 번호가 더 작은 공의 색을 따른다.

예를 들어 컨테이너에 (3, 빨강), (6, 검정), (12, 빨강), (14, 검정) 공이 있다고 하자. (9, 무색) 공을 넣으면 가장 가까운 유색 공은 (6, 검정)이므로 이 공은 검정이 된다. 그러면 컨테이너에는 (3, 빨강), (6, 검정), (9, 검정), (12, 빨강), (14, 검정)이 남는다. 이어서 (10, 무색) 공을 넣으면 가장 가까운 (9, 검정)을 따라 검정이 된다. 최종적으로 빨강 2개, 검정 4개가 된다.

결과는 넣는 순서에 따라 달라진다. 위 예에서 (10, 무색) 공을 먼저 넣으면 최종적으로 빨강 4개, 검정 2개가 된다.

입력

첫 줄에 정수 $N$ 과 $M$ 이 주어진다( $1 \le N, M \le 50$ ).

다음 $N$ 개의 줄에는 정수 $A_i$ 와 색 $S_i$ 가 주어진다( $0 \le A_i \le 10^9$ , $S_i$ 는 RED 또는 BLACK). 이는 $i$ 번째 유색 공의 번호와 색이다.

마지막 줄에는 무색 공의 번호 $B_i$ 가 $M$ 개 주어진다( $0 \le B_i \le 10^9$ ). 유색 공과 무색 공의 번호는 모두 서로 다르다.

출력

무색 공을 모두 컨테이너에 넣었을 때 빨강 공이 검정 공보다 엄격하게 많아지는 순서의 수를 구하여, 998244353으로 나눈 나머지를 한 줄에 출력한다. 공은 한 번에 하나씩만 넣을 수 있다. $i$ 번째로 넣는 공이 하나라도 다르면 서로 다른 순서로 본다.

예제2

예제 1
입력
```
2 3
1 BLACK
10 RED
2 5 7
```
예상 출력
```
3
```
예제 2
입력
```
2 3
1 RED
10 BLACK
2 4 7
```
예상 출력
```
6
```