기차 배차 문제

Bessie는 기차 배차 담당자로 새 일을 맡았다. 역은 $A$와 $B$ 두 곳이 있고, 예산 문제로 두 역을 잇는 선로는 하나뿐이다. 기차가 시각 $t$에 한 역에서 출발하면 다른 역에는 시각 $t+T$에 도착한다 ($1\le T\le 10^{12}$).

출발 시각을 정해야 하는 기차는 $N$대이다 ($1\le N\le 5000$). $i$번째 기차는 역 $s_i$에서 시각 $t_i$ 이후에 출발해야 한다 ($s_i\in \{A, B\}$, $0\le t_i\le 10^{12}$).

서로 반대 방향으로 달리는 기차는 같은 시각에 선로 위에 있을 수 없다. 두 기차가 충돌하기 때문이다. 같은 방향으로 가는 기차는 같은 시각에 여러 대가 선로를 달려도 된다. 기차의 크기는 무시할 만큼 작다고 가정한다.

첫 줄에 $N$과 $T$가 주어진다. 이후 $N$개의 줄에는 각각 $i$번째 기차의 역 $s_i$와 시각 $t_i$가 주어진다.

가능한 모든 운행 계획 가운데 전체 지연 시간의 최솟값을 출력한다. $i$번째 기차가 시각 $a_i\ge t_i$에 출발하면 전체 지연 시간은 $\sum_{i=1}^N(a_i-t_i)$이다.