题目描述

背景设定

在浩瀚的宇宙中，人类在"地球"（编号0）建立了星际探险总部。为了探索宇宙的奥秘，总部派出了最先进的无人探测器前往其他星球收集数据。宇宙中存在编号1至n+1的星球，其中n+1号星球环境恶劣，无需探测。1至n号星球上隐藏着古老的能量核心，激活这些核心需要消耗对应的能量值$a_i$。

任务描述

探测器从地球出发，配备初始能量c。在编号为i的星球上，探测器可以进行以下操作：

1. 移动：
   • 向左移动至i-1号星球，消耗1单位能量
   • 向右移动至i+1号星球，消耗1单位能量
2. 激活核心：
   • 激活后可直接返回地球或前往n+1号星球（需消耗$a_i$能量）
   • 每个能量核心只能激活一次
   • 能否前往n+1号星球由系统参数k决定（$k=1$允许，$k=0$禁止）

任务目标

在保证探测器正常运行（能量不耗尽）的前提下，计算最多能激活多少个能量核心。

输入格式

• 第一行：两个整数n（星球数量）和c（初始体力值）。
• 第二行：一个整数k（能否传送到n+1号星球的标志）。
• 第三行：n个整数$a_{1}$,$a_{2}$,…,$a_n$（每个星球的传送阵消耗的体力值）。

输出格式

• 一行，一个整数，表示最多能使用传送阵的次数。

样例输入

5 6
0
1 1 1 1 1

样例输出

2

提示

$1\le n\le 2\times 10^{5},0\le k\le 1,1\le c,a_i\le 10^{9}$。

5 6
0
1 1 1 1 1

2

5 5
0
1 1 1 1 1

2

5 6 
0 
1 1 1 1 1

2