题目描述

题目译自 Open Olympiad in Informatics 2018 Day1 T3 「Отбой / Curfew」。

夏季某校的教师们正在安排学生就寝。

宿舍由 $n$ 个房间组成，每个房间必须恰好住 $b$ 名学生。然而，在熄灯时，许多学生并不在自己的房间里。房间按顺序排列，编号从 $1$ 到 $n$，初始时第 $i$ 个房间有 $a_i$ 名学生。宿舍内所有的学生都在且仅在这些房间中，即 $a_1 + a_2 + \ldots + a_n = nb$。宿舍中还住着 $p$ 名教师，且 $p \leq 2$。

安排学生就寝的过程如下。一名教师站在 $1$ 号房间并向 $n$ 号房间方向移动。如果有第二名教师，则他站在 $n$ 号房间并向 $1$ 号房间方向移动。完成一个房间的安排后，教师会移动到下一个房间。如果有两名教师，他们会同时进入和离开各自的房间。如果 $n$ 为奇数且有两名教师，则中间房间仅由第一名教师负责安排。所有学生就寝后，过程结束。

当教师进入房间时，他会清点房间内的学生人数，然后熄灯并锁门。此外，如果房间内的学生人数与 $b$ 不符，该教师会将房间编号记录在自己的笔记本中，但仍会熄灯并锁门。教师们急于制定明天的教学计划，因此只关注学生人数而不关心具体是哪些学生。

在教师们进入房间期间，学生可以在尚未锁门且当前未被安排的房间之间移动，每次移动的距离不得超过 $d$ 个房间（即移动到的房间编号与当前房间编号之差不超过 $d$）。此外，在移动后（或不移动），任何学生都可以选择在当前房间的床下藏身，这样教师在清点时不会看到他们。每个房间的床下可以同时藏任意数量的学生。

具体而言，过程如下：

• 宣布熄灯，此时第 $i$ 个房间有 $a_i$ 名学生。
• 每个学生可以移动到另一个房间，但移动距离不得超过 $d$，或留在当前房间。之后，愿意藏身的学生可以藏到床下。
• 教师进入 $1$ 号房间（如果有两名教师，则另一名同时进入 $n$ 号房间），安排房间内所有学生就寝并锁门（之后无法进出该房间）。
• 学生可以从 $2$ 号到 $n$ 号房间（或到 $n-1$ 号房间，如果有两名教师）移动到其他房间，移动距离不得超过 $d$，或留在当前房间。愿意藏身的学生可以藏到床下。
• 教师从 $1$ 号房间移动到 $2$ 号房间（如果有两名教师，则另一名从 $n$ 号房间移动到 $n-1$ 号房间）。
• 过程持续，直到所有房间的学生都被安排就寝。

设 $x_i$ 表示第 $i$ 名教师记录的可见人数违规的房间数量。学生们知道，宿舍主任只会听取一名教师对熄灯期间混乱情况的投诉，因此他们希望采取行动，使 $x_i$ 中的最大值尽可能小。帮助他们确定，在学生采取最优行动时，这一最大值的最小可能值是多少。

输入格式

第一行包含四个整数 $p, n, d, b$ $(1 \leq p \leq 2, 2 \leq n \leq 100000, 1 \leq d \leq n-1, 1 \leq b \leq 10000)$，分别表示教师数量、宿舍房间数量、学生一次移动的最大房间数以及每个房间所需的学生数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^{9})$，表示宣布熄灯前第 $i$ 个房间的学生数量。

保证 $a_1 + a_2 + \ldots + a_n = nb$。

输出格式

输出一个数字，即 $x_i$ 的最大值在学生采取最优行动时的最小可能值。

1 5 3 1
0 0 0 5 0

0

在第一个样例中，学生移动速度足够快，可以在教师进入第一间房间之前分散到各自的房间，因此答案为 $0$。

1 5 3 10
5 1 1 1 42

1

在第二个样例中，教师至少会记录一个房间到笔记本中。一种最优策略如下：在教师进入第一间房间之前，从第五间房间各有 $10$ 名学生移动到第二、三、四间房间。随后，在第二、三、四间房间各有一名学生藏到床下，在第五间房间有两名学生藏到床下，之后学生不再采取任何行动。在这种情况下，教师只会记录第一间房间。

2 5 1 1
1 0 0 0 4

1

在第三个样例中，前三个房间由第一名教师负责，后两个房间由第二名教师负责。一种最优解决方案如下：第一步，三名学生从第五间房间移动到第四间房间；第二步，其中两名学生移动到第三间房间，一名学生在那里藏身。这样，第一名教师只会因第二间房间不满，而第二名教师完全不会遇到违规情况。

2 6 1 2
3 8 0 1 0 0

2

在第四个样例中，一种最优策略如下：第一步，第一间房间的所有学生藏身，第二间房间的所有学生移动到第三间房间；第二步，一名学生从第三间房间移动到第四间房间，另外 $5$ 名学生藏身。这样，第一名教师会对第一和第二间房间不满，第二名教师会对第五和第六间房间不满。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。