题目描述

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

你初始时位于小镇 $S$。你可以反复通过道路在由同一条道路相连的两个小镇之间移动。

求在移动距离总和不超过 $L$ 的前提下，一次移动过程中访问的小镇数量的最大值。这里，小镇 $S$ 也算作被访问的小镇之一，同一个小镇即使被多次访问也只计一次。

输入格式

输入按以下格式从标准输入读入：

• $N$ $S$ $L$
• $A_1$ $A_2$ $\ldots$ $A_{N - 1}$

输出格式

输出答案。

数据范围

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

6 3 10
5 2 4 1 6

4

你初始时位于小镇 $3$。若按小镇 $3 \to 2 \to 3 \to 4 \to 5$ 的顺序移动，则移动距离的总和为 $2 + 2 + 4 + 1 = 9$，访问的小镇为 $2, 3, 4, 5$，共 $4$ 个。

由于无法在移动距离总和不超过 $10$ 的前提下访问 $5$ 个或更多小镇，因此该情况下的答案为 $4$。

8 8 17
2 3 4 4 3 5 1

6

2 1 1000000000000000000
10000

2

9 6 28
5 4 9 2 3 6 1 4

6

• 来源：AtCoder ABC 475 C

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（70 分）：无特殊限制。