Train Scheduling

문제

Bessie has taken on a new job as a train dispatcher! There are two train stations: $AA$ and $BB$. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time $tt$, then it will arrive at the other station at time $t+Tt+T$ ($1\le T\le {10}^{12}1\backslash le\; T\backslash le\; 10^\{12\}$).

There are $NN$ ($1\le N\le 50001\backslash le\; N\backslash le\; 5000$) trains whose departure times need to be scheduled. The $ii$th train must leave station $s_{i}s\_i$ at time $t_{i}t\_i$ or later ($s_i\in \{A,B\},0\le t_i\le {10}^{12}s\_i\backslash in\; \backslash \{A,\; B\backslash \},\; 0\backslash le\; t\_i\backslash le\; 10^\{12\}$). It is not permitted to have trains going in opposite directions along the track at the same time (since they would crash). However, it is permitted to have many trains on the track going in the same direction at the same time (assume trains have negligible size).

Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train $ii$ is scheduled to leave at time $a_i\ge t_{i}a\_i\backslash ge\; t\_i$, the total delay is defined as ${\sum }_{i=1}^N(a_i-t_i)\backslash sum\_\{i=1\}^N(a\_i-t\_i)$.

입력

The first line contains $NN$ and $TT$.

Then $NN$ lines follow, where the $ii$th line contains the station $s_{i}s\_i$ and time $t_{i}t\_i$ corresponding to the $ii$th train.

출력

The minimum possible total delay over all valid schedules.