P15598 [ICPC 2020 Jakarta R] Red Black Ball

There are $N + M$ color-shifting balls uniquely numbered between $0$ and $10^9$, inclusive. Among those, $N$ balls have a solid red or solid black color (also referred to as colored balls), and $M$ balls have an open-color. A ball with an open-color will shift its color into either red or black if it is put into a container together with at least one colored ball. Specifically, the open-color ball will shift its color into the same color as the colored ball in the container which has the closest number (i.e. minimum absolute difference) to the open-color ball number. If there are two colored ball numbers with the same absolute difference with the open-color ball number, the open-color ball number will shift its color into the same color as the colored ball which has the less number between the two. For example, let there be 4 colored balls in a container: $(3,\text{red})$, $(6,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. If we put an $(9,\text{open})$ ball into the container, then it will shift its color into black because $(6,\text{black})$ is the colored ball in the container with the lowest closest number to $(9,\text{open})$. After this, there becomes 5 colored balls in the container: $(3,\text{red})$, $(6,\text{black})$, $(9,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. Next, if we put a $(10,\text{open})$ ball into the container, then it will shift its color into black because $(9,\text{black})$ is the colored ball in the container with the lowest closest number to $(10,\text{open})$. After this, there becomes 6 colored balls in the container: $(3,\text{red})$, $(6,\text{black})$, $(9,\text{black})$, $(10,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. In this example, the container ends up with 6 colored balls with 2 red balls and 4 black balls. Notice that the final result might be different if we put the open-color balls in a different order. In the previous example, if we put $(10,\text{open})$ first before $(9,\text{open})$, then the container ends up with 4 red balls and 2 black balls. Given $N$ colored balls in a container and $M$ open-color balls, your task in this problem is to determine the number of ways to put **all** open-color balls into the container such that the container ends up with **strictly** more red balls than black balls. Two ways are considered different if and only if there exists an $i$ such that the $i^\text{th}$ open-color ball put into the container is different. Note that you can only put the open-color balls into the container one by one.

Input begins with a line containing two integers: $N\ M$ ($1 \leq N, M \leq 50$) representing the number of colored balls and the number of open-color balls, respectively. The next $N$ lines each contains an integer and a string: $A_i\ S_i$ ($0 \leq A_i \leq 10^9$; $S_i \in \{\text{RED}, \text{BLACK}\}$) representing the number and color of the $i^\text{th}$ ball, respectively. The next line contains $M$ integers: $B_i$ ($0 \leq B_i \leq 10^9$) representing the number of the open-color balls. It is guaranteed that there are no balls (both colored and open-color) which have the same number, i.e. $|A \cup B| = N + M$ where $A$ is the set of all unique numbers on the colored balls and $B$ is the set of all unique numbers on the open-color balls.

Output in a line an integer representing the number of ways to put all the open-color balls into the container such that the container ends up with strictly more red balls than black balls, modulo $998\,244\,353$.

#### Explanation for the sample input/output #1 There are 3 ways to put all the open-color balls such that the container ends up with strictly more red balls than black balls. - $(2,\text{open}), (7,\text{open}), (5,\text{open}) \rightarrow 3$ red and $2$ black balls - $(7,\text{open}), (2,\text{open}), (5,\text{open}) \rightarrow 3$ red and $2$ black balls - $(7,\text{open}), (5,\text{open}), (2,\text{open}) \rightarrow 3$ red and $2$ black balls #### Explanation for the sample input/output #2 Regardless of how we put all the open-color balls, the container will always end up with more red balls than black balls.