题目描述

Squeaky 老鼠是宇宙飞船的船长，正在执行探索太阳系边界的任务。飞船呈长条状，沿着飞船的长度方向有一条笔直的通道，$N$ 个舱室连接在通道的不同位置。舱室从左到右编号为 $1$ 到 $N$，相邻舱室之间的距离不一定相等。

每个舱室 $i$（$1 \leq i \leq N$）中都有重要的设备，用于支持飞船的运行，设备的重要性用正整数 $v_i$ 表示。相邻舱室之间有电缆连接，设备可以通过其他舱室远程控制。

然而，一场太阳风暴即将袭击飞船！太阳风暴会释放大量带电粒子，如果不加保护，将会损坏飞船上的设备。

幸运的是，船员随船携带了 $S$ 个防护盾。每个防护盾可以放置在任意舱室，也可以选择不使用。每个防护盾能在其所在位置产生磁场，保护半径为 $K$ 米，半径范围内的所有舱室设备都能被保护（包括防护盾所在的舱室）。

需要注意：

• 通道本身无需保护，因为电缆不受带电粒子的影响；
• 为了方便后续操作，Squeaky 希望所有被保护的舱室之间可以相互控制设备；
• 具体而言，如果两个被保护的舱室之间存在未被保护的舱室，则无法相互控制设备，这是不允许的。

请你作为工程师，帮助 Squeaky 确定防护盾的最优放置方案，最大化被保护舱室的重要性总和，并保证控制连通性。

输入格式

第一行三个整数 $N,\ S,\ K$，分别表示舱室数量、防护盾数量、防护盾的保护半径（单位：米）。

第二行 $N - 1$ 个整数 $d_i$，第 $i$ 个舱室与第 $i+1$ 个舱室之间的距离。

第三行 $N$ 个整数 $v_i$，第 $i$ 个舱室的重要性。

输出格式

第一行一个整数 $T$，表示实际使用的防护盾数量，$0 \leq T \leq S$。

第二行 $T$ 个整数，表示放置防护盾的舱室编号，顺序不限。若有多种方案都能达到最优，输出任意一种均可。

6 2 7
10 4 7 18 11
5 8 2 4 8 12

2
3 5

6 2 38
10 4 7 18 11
5 8 2 4 8 12

1
4

6 1 12
10 4 7 18 11
5 8 2 4 8 12

1
5

12 1 2
1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 6 5 4 3 2 1

1
6

10 3 1
2 2 2 2 2 2 2 2 2
3 7 5 6 8 4 3 2 2 9

3
3 4 5

提示

【样例解释】

对于样例 #1：

飞船的结构如下：

部署两个防护盾的最优位置是在第 $3$ 和第 $5$ 个舱室。

第 $3$ 个舱室的防护盾将保护第 $2, 3, 4$ 个舱室；第 $5$ 个舱室的防护盾将保护第 $5$ 个舱室。

注意，舱室 $4$ 和 $5$ 之间的通道没有完全被保护，这是允许的，因为通道上的电缆不会受到损害。

请注意，如果将两个防护盾部署在第 $3$ 和第 $6$ 个舱室，这不是一个合法方案，因为第 $5$ 个舱室会被太阳风暴损坏，导致第 $6$ 个舱室的船员无法控制第 $2, 3, 4$ 个舱室的设备。

对于样例 #2：

飞船的结构与样例 $1$ 相同，但防护盾的半径更大。

在第 $4$ 个舱室部署一个防护盾足以保护所有舱室。

注意，还有许多其他可接受的方案。

其他一些可选方案包括：

• 仅在第 $3$ 个舱室部署一个防护盾；
• 分别在第 $3$ 和第 $5$ 个舱室各部署一个防护盾；
• 在第 $3$ 个舱室部署两个防护盾。

所有能够最大化被保护舱室总重要性的合法方案都会被接受。

对于样例 #3：

飞船的结构与样例 $1$ 相同。

在第 $5$ 个舱室部署防护盾可以保护第 $5$ 和第 $6$ 个舱室，这是最优方案。

注意，同样也可以选择将防护盾部署在第 $6$ 个舱室，这也是最优的。

对于样例 #4：

最优方案是在第 $6$ 个舱室部署防护盾，这将保护第 $4, 5, 6, 7, 8$ 个舱室。

注意，同样也可以选择在第 $7$ 个舱室部署防护盾，这也是最优的。

对于样例 #5：

部署三个防护盾的最优位置是第 $3, 4, 5$ 个舱室。

【数据范围】

• $1 \leq S \leq N \leq 10^6$
• $1 \leq K \leq 10^{12}$
• $1 \leq d_i \leq 10^6$
• $1 \leq v_i \leq 10^6$

子任务编号	分值	附加限制
$1$	$10$	$S = 1,\ N \leq 10^4,\ K \leq 10^9,\ d_i \leq 10^5,\ v_i \leq 10^5$
$2$	$7$	$S = 1,\ d_i = 1$
$3$	$11$	$S = 1$
$4$	$8$	$K = 1,\ d_i = 2$
$5$	$18$	$N \leq 10^4$
$6$	$16$	$S \leq 50$
$7$	$30$	无附加限制