分数: 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