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