{"problem":{"name":"[USACO23DEC] Train Scheduling P","description":{"content":"Bessie 找到了一份行车调度的新工作。现在有两座火车站 $A$ 和 $B$，由于预算限制，只有一条单线铁道连接起车站 $A$ 和 $B$。如果一列列车在 $t$ 时刻离开其中一座火车站，它将在 $t+T$（$1 \\le T \\le 10^{12}$）时刻到达另一座火车站。 现在有 $N$（$1 \\le N \\le 5000$）列火车的出发时间需要安排。第 $i$ 列火车必须在 $t_i$ 时","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9985"},"statements":[{"statement_type":"Markdown","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}$。\n\n## Input\n\n第一行包含 $N$ 和 $T$。\n\n接下来 $N$ 行，第 $i$ 行包含用于描述第 $i$ 辆列车的 $s_i,t_i$。\n\n## Output\n\n输出合法安排中最小总延误时间。\n\n[samples]\n\n## Background\n\n**Note: The memory limit for this problem is 512MB, twice the default.**\n\n## Note\n\n### 样例解释 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$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9985","tags":["动态规划 DP","USACO","2023","O2优化","动态规划优化"],"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"]],"created_at":"2026-03-03 11:09:25"}}