题目描述

众所周知，狗的故乡是遥远的星球“汪星”，小珅和小泽作为汪星的超级无敌帅帅侦查员，来到地球为了收集情报。成功征服地球后，汪星有了征服宇宙的打算，决定派出得力侦查员去收集其他星球的情报。

具体而言，除“汪星”外，宇宙中还有 $n+1$ 颗星球，这些星球与汪星都在一条直线上，依次编号为 $1,2,3,\dots,n+1$，“汪星”编号为 $0$。编号为 $n+1$ 的星球不适合居住，因此没有被任何势力占领也不需要收集该星球的情报。由于“汪星”科技发达，在编号 $1 \sim n$ 的每个星球中都隐形的传送阵，编号为 $i$ 的星球上的传送阵需要消耗 $a_i$ 点体力值。

侦查员从“汪星”出发开始去收集其他星球的情报，假设侦查员现在在编号为 $i$ 的星球上，那么下一步可以进行如下三种操作：

• 向左移动到编号为 $i-1$ 的星球，消耗 $1$ 点体力值。
• 向右移动到编号为 $i+1$ 的星球，消耗 $1$ 点体力值。
• 从编号为 $i$ 的星球直接传送到“汪星”或编号为 $n+1$ 的星球，消耗 $a_i$ 点体力值，并且每个传送阵只能使用一次。

注意：因为受到星球自转的影响，有时候不能直接传送到编号为 $n+1$ 的星球。

每次侦查员外出收集情报时的初始体力值为 $c$，综合各方面因素考虑，侦查员需要尽可能的多次使用传送阵才能在收集情报的同时保证自身安全，注意中途可能会传送到“汪星”，此时不会有任何体力值的补充，毕竟侦查员也不想无休止的工作下去，也不需要考虑侦查员最后是否要一定回到“汪星”。

因此，汪星皇决定邀请你，来帮助他计算侦查员最多能够使用几次传送阵。

输入格式

第一行，包含两个整数 $n,c$。

第二行，包含一个整数 $k$，表示侦查员本次收集情报时是否可以传送到编号为 $n+1$ 的星球，$k=1$ 表示可以传送，$k=0$ 表示不能传送。

第三行，包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

一行，一个整数表示答案。

输入输出样例

5 6
0
1 1 1 1 1

2

8 32
0
100 52 13 6 9 4 100 35

2

8 32
1
100 52 13 6 9 4 100 35

3

说明/提示

说明/提示

样例 1 解释：从“汪星”出发先向右移动到编号为 $1$ 的星球，然后使用 $1$ 号星球的传送阵回到“汪星”，再从“汪星”出发先向右移动到编号为 $2$ 的星球，然后使用 $2$ 号星球的传送阵回到“汪星”。此时侦查员只剩下 $6-1-1-2-1=1$ 点体力值，没有足够的体力值使用另一个星球的传送阵了。因此最多只能使用 $2$ 次传送阵。

样例 2 解释：从“汪星”出发先向右移动到编号为 $4$ 的星球，然后使用 $4$ 号星球的传送阵回到“汪星”，再从“汪星”出发先向右移动到编号为 $6$ 的星球，然后使用 $6$ 号星球的传送阵回到“汪星”。此时侦查员只剩下 $32-4-6-6-4=12$ 点体力值，没有足够的体力值使用另一个星球的传送阵了。因此最多只能使用 $2$ 次传送阵。

样例 3 解释：从“汪星”出发先向右移动到编号为 $4$ 的星球，然后使用 $4$ 号星球的传送阵回到第 $n+1$ 个星球，再从第 $n+1$ 个星球出发先向左移动到编号为 $6$ 的星球，然后使用 $6$ 号星球的传送阵回到第 $n+1$ 个星球，再从第 $n+1$ 个星球出发先向左移动到编号为 $7$ 的星球，然后使用 $7$ 号星球的传送阵回到“汪星”。此时侦查员只剩下 $32-4-6-3-4-4-9=2$ 点体力值，没有足够的体力值使用另一个星球的传送阵了。因此最多只能使用 $3$ 次传送阵。

数据范围

对于 $30\%$ 的数据保证：$1 \le n \le 1000$。

另外 $40\%$ 的数据保证：$k=0$。

对于 $100\%$ 的数据保证：$1 \le n \le 2 \times 10^5,0 \le k \le 1,1 \le c,a_i \le 10^9$。