[USACO23DEC] Train Scheduling P

Bessie 找到了一份行车调度的新工作。现在有两座火车站 $A$ 和 $B$，由于预算限制，只有一条单线铁道连接起车站 $A$ 和 $B$。如果一列列车在 $t$ 时刻离开其中一座火车站，它将在 $t+T$（$1 \le T \le 10^{12}$）时刻到达另一座火车站。 现在有 $N$（$1 \le N \le 5000$）列火车的出发时间需要安排。第 $i$ 列火车必须在 $t_i$ 时刻后从车站 $s_i$ 出发（$s_i\in \{A,B\}$，$0 \le t_i \le 10^{12}$）。在同一时刻不允许铁道上有相反方向的列车，否则它们会相撞。但是，假设火车有可以忽略的尺寸，在同一时刻，铁道上可以有许多相同方向的列车。 帮助 Bessie 安排每辆列车的出发时间，在不会相撞的前提下最小化总延误时间。假设第 $i$ 辆列车被安排在 $a_i$ 时刻出发，总延误为 $\sum\limits_{i=1}^n{a_i-t_i}$。 ## Input 第一行包含 $N$ 和 $T$。 接下来 $N$ 行，第 $i$ 行包含用于描述第 $i$ 辆列车的 $s_i,t_i$。 ## Output 输出合法安排中最小总延误时间。 [samples] ## Background **Note: The memory limit for this problem is 512MB, twice the default.** ## Note ### 样例解释 1 唯一的一辆列车准点出发。 ### 样例解释 2 有两种最佳方案。第一种是让列车 $2,3,4$ 准点出发，列车 $1$ 延误一分钟后出发。第二种是让列车 $1,2,3$ 准点出发，列车 $4$ 延误一分钟后出发。 ### 样例解释 3 最佳方案是让列车 $1,3$ 准点出发，列车 $2$ 在时刻 $13$ 出发，列车 $4$ 在时刻 $23$ 出发。总延误为 $0+11+0+2=13$。 ### 测试点性质 - 测试点 $5-6$ 满足 $N \le 15$。 - 测试点 $7-10$ 满足 $N \le 100$。 - 测试点 $11-14$ 满足 $N \le 500$。 - 测试点 $15-18$ 满足 $N \le 2000$。 - 测试点 $19-24$ 没有额外限制。