题目描述

有 $N$ 个城镇排列在一条直线上，编号为 $1, 2, \ldots, N$。对每个满足 $1 \le i \le N-1$ 的整数 $i$，城镇 $i$ 与城镇 $i+1$ 之间有一条长度为 $A_i$ 的道路相连。

你最初位于城镇 $S$。你可以反复地沿着道路在相连的两个城镇之间移动。

在移动距离的总和不超过 $L$ 的前提下，请求出一连串移动中访问过的城镇数量的最大值。其中城镇 $S$ 也算作访问过，同一个城镇访问多次只计 $1$ 次。

输入格式

N S L
A_1 A_2 ... A_{N-1}

输出格式

输出答案。

输入示例 1

6 3 10
5 2 4 1 6

输出示例 1

4

示例 1 说明

最初位于城镇 $3$。按 $3 \to 2 \to 3 \to 4 \to 5$ 的顺序移动，总距离为 $2+2+4+1=9$，访问过的城镇是 $2,3,4,5$ 共 $4$ 个。

在总距离不超过 $10$ 的前提下无法访问 $5$ 个及以上的城镇，所以答案是 $4$。

注意为了从左侧折返到右侧，中间那段路被走了两次（$3 \to 2$ 和 $2 \to 3$ 各走一次长度 $2$ 的路）。

输入示例 2

8 8 17
2 3 4 4 3 5 1

输出示例 2

6

示例 2 说明

起点在最右端的城镇 $8$，只能一路向左，不存在折返。此时总距离就是单程距离，$17$ 恰好够走到城镇 $3$，共 $6$ 个城镇。这组数据用来检验起点在端点时的处理。

输入示例 3

2 1 1000000000000000000
10000

输出示例 3

2

示例 3 说明

$L$ 取到上限 $10^{18}$，远大于全部道路长度之和，所以能走遍所有城镇。这组数据用来检验是否使用了 long long：用 int 读入 $L$ 会直接溢出。

输入示例 4

9 6 28
5 4 9 2 3 6 1 4

输出示例 4

6

示例 4 说明

最优方案需要先往右再折返向左（或反之），而不是单向直走。这组数据用来检验是否比较了两种折返顺序：只考虑其中一种会得到 $5$。

约束条件

• $2 \le N \le 8000$
• $1 \le S \le N$
• $0 \le L \le 10^{18}$
• $1 \le A_i \le 10^9$
• 所有输入值均为整数