← 返回题目列表

AtCoder · agc011_f

F. 列车服务规划

中文机器翻译题面 查看原题

分数: 1700 点

问题陈述

高桥王国有一条铁路。 该铁路由 N 部分,编号 1, 2, ..., N,和 N+1 站,编号 0, 1, ..., N。部分 i 直接连接车站 i-1 和 i。 火车正好需要 A_i 完成部分的分钟数 i,无论方向如何。 每个 N 部分要么在整个长度上单轨,要么在整个长度上双轨。 如果 B_i = 1,部分 i 是单轨的;如果 B_i = 2,部分 i 是双轨制的。 两列相反方向运行的列车可以在双线路段交叉,但不能在单线路段交叉。 火车也可以在车站交叉。

Snuke 正在为这条铁路制定时间表。在这个时刻表中,该铁路上的列车每 K 分钟,如下图所示。这里,粗线代表火车在铁路上运行的位置。 (有关说明,请参阅示例 1。)

创建此类时刻表时,求火车出发车站所需时间的最小总和 0 并到达车站 N,以及火车离开车站所需的时间 N 并到达车站 0。 可以证明,如果存在满足本问题条件的时间表,则这个最小和总是整数。

正式而言,火车到达和出发的时间必须满足以下条件:

  • 每趟列车要么出发车站 0 开往车站 N,或出发车站 N 开往车站 0.
  • 每趟列车恰好需要 A_i 完成部分的分钟数 i。例如,如果一列火车开往车站 N 出发站 i-1 时间 t,火车到站 i 正好在时间 t+A_i.
  • 假设一列火车开往车站 N 到达车站时间 s,发车时间 t。然后,下一班开往车站的火车 N 到达车站时间 s+K,发车时间 t+K。另外,前一班开往车站的火车 N 到达车站时间 s-K,发车时间 t-K。对于开往车站的火车也必须如此 0.
  • 反方向行驶的列车不得同时在同一单线路段(两端车站除外)上行驶。

约束

  • 1 \leq N \leq 100000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • A_i 是一个整数。
  • B_i 是 1 or 2.

部分分数

  • 在测试集中值得 500 点,所有路段均为单轨。也就是说, B_i = 1.
  • 在测试集中值得另一个 500 点, N \leq 200.

输入

输入由标准输入按以下格式给出:

N K
A_1 B_1
A_2 B_2
:
A_N B_N

输出

打印一个整数,表示火车出发所需时间的最小总和 0 并到达车站 N,以及火车离开车站所需的时间 N 并到达车站 0。 如果无法创建满足条件的时间表,则打印 -1 代替。


样本输入 1

3 10
4 1
3 1
4 1

示例输出 1

26

例如,相关时间量的总和将为 以下时间表中的 26 分钟:

本时刻表中,红线代表的列车出发站 0 时间 0,到达车站 1 时间 4, 出发车站 1 时间 5,到达车站 2 时间 8,等等。


示例输入 2

1 10
10 1

示例输出 2

-1

示例输入 3

6 4
1 1
1 1
1 1
1 1
1 1
1 1

示例输出 3

12

示例输入 4

20 987654321
129662684 2
162021979 1
458437539 1
319670097 2
202863355 1
112218745 1
348732033 1
323036578 1
382398703 1
55854389 1
283445191 1
151300613 1
693338042 2
191178308 2
386707193 1
204580036 1
335134457 1
122253639 1
824646518 2
902554792 2

示例输出 4

14829091348