← 返回题目列表

Codeforces · 730/D

D. 跑过桥

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

Polycarp 正在玩一款名为“Running Over The Bridges”的游戏。在这个游戏中他必须从左到右跑过n座桥。桥接连排列,因此第 i 个桥从第 (i - 1) 个桥结束的地方开始。

您有以下有关桥梁的数据: li 和 ti — 第 i 座桥的长度以及 Polycarp 可以在第 i 座桥上奔跑的最大允许时间。因此,如果波利卡普在时间 T 位于桥 i 的开头,那么他必须在时间 T + ti 或更早的时间离开它。允许它在时间 T + ti 精确地到达桥的右端。

波利卡普可以以 0.5 的速度从左侧跑到右侧,因此他会在 2·s 的时间内跑过一座长度为 s 的桥。除此之外,他还有几种神奇的饮品。如果他喝了一杯,他的速度会增加两倍(即值 1),持续 r 秒。所有神奇饮料都是相同的。请注意,波利卡普只能在整数时刻喝饮料,而且他会立即喝完。另外,如果Polycarp在T时刻喝了一杯饮料,他可以在不早于T+r时刻喝下一杯饮料。

波利卡普跑过所有 n 座桥所需的最少饮料数量是多少?如果这个数字不大于105,那么你必须找出坡旅甲必须使用每种魔法饮料的时刻。

输入

第一行包含两个整数 n 和 r (1 ≤ n ≤ 2·105, 1 ≤ r ≤ 1012) — 桥的数量和魔法饮料的效果持续时间。

第二行包含整数序列 l1, l2, ..., ln (1 ≤ li ≤ 5·106),其中 li 等于第 i 个桥的长度。

第三行包含整数序列 t1, t2, ..., tn (1 ≤ ti ≤ 107),其中 ti 等于 Polycarp 在第 i 座桥上运行所允许的最大时间。

输出

输出的第一行应包含 k — Polycarp 必须使用的最少饮料数量,如果没有解决方案,则为 -1。

如果解存在并且 k 的值不大于 105,则在下一行输出 k 个整数 - 从游戏开始时 Polycarp 必须使用饮料的时刻。按时间顺序打印时间点。如果有多个解,则可以输出任意一个。

示例

输入 #1

1 3
7
10

输出 #1

2
0 3

输入 #2

3 3
3 3 3
3 3 2

输出 #2

-1

输入 #3

3 100000
5 5 5
5 7 8

输出 #3

1
0

输入#4

4 1000
1 2 3 4
10 9 10 9

输出#4

0

注意

在第一种情况下,只有一座桥,很明显波利卡普在没有魔法饮料的情况下无法跑过它。因此,如果他在开始时(时间 0 时刻)使用一杯魔法饮料,并在三秒后(时间 3 时刻)使用第二杯,他将能够及时到达桥的尽头。请注意,在这种情况下,该问题有多种可能的答案。例如,Polycarp 可以在时间 4 时使用第一杯饮料,并在时间 7 时使用第二杯。

在第二种情况下,波利卡普即使使用魔法饮料也无法跑过所有桥梁。因此,本例的答案是-1。

在第四种情况下,坡旅甲可以在没有魔法饮料的情况下跑过所有桥梁。