该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

奇异星球上正处于战争状态，A阵营和B阵营的士兵们在长度为 $m$ 的独木桥上展开了一场遭遇战。

两方的士兵共计 $n$ 名，他们在独木桥上的位置各不相同，具体的，A阵营的士兵用字母 “A” 加上一串数字 $w_i$ 表示该士兵在独木桥上的位置，B阵营的士兵则是用字母 “B” 加上一串数字 $w_i$表示位置。

现在双方一起停战撤兵，A阵营的士兵都会往左移动撤离独木桥，B阵营的士兵都会往右移动撤离独木桥。请问直到所有士兵都撤离完毕，两方阵营的士兵在这过程中一共发生了几次“交错”？

注：“交错” 指不同阵营的两个士兵的左右关系发生变化，例如 A5 原本在 B2 的右侧，撤离时 A5 往左，B2 往右，就会产生一次 “交错”。

输入格式

第一行两个整数 $n, m$，表示桥上士兵的总数量和桥的总长度。

接下来 $n$ 行，每行一个表示士兵阵营和位置的字符串，字符串规则见题目描述。

输出格式

所有士兵都撤离完毕共产生的 “交错” 次数。

样例数据

2 10
A5
B2

1

3 50
B7
A6
B50

0

数据范围

对于 $20\%$ 的数据，$n=2$

对于 $50\%$ 的数据，$m\le 100$

对于 $80\%$ 的数据，$2\le n \le 1000, 2\le m\le 10^5$

对于全部的数据，$2\le n \le 10^6, 2 \le m \le 10^9, 0\le w_i \lt m$，数据保证 $w_i$ 两两不同。