AT_abc475_c.Walk the Line

There are $N$ towns arranged in a line. The towns are numbered $1, 2, \ldots, N$, and for each integer $i$ satisfying $1 \leq i \leq N-1$, town $i$ and town $i + 1$ are connected by a road of length $A_i$.

You are initially at town $S$. You can repeatedly move between two towns connected by a road using that road.

Find the maximum possible number of towns visited in a sequence of moves such that the total distance traveled is at most $L$. Here, town $S$ is included among the towns visited, and a town visited multiple times is counted only once.

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

你初始位于城镇 $S$。你可以反复利用道路在两个相连的城镇之间移动。

求在总行驶距离不超过 $L$ 的前提下，通过一系列移动最多能访问多少个不同的城镇。注意：起始城镇 $S$ 被计入已访问城镇；若某个城镇被多次访问，仅计一次。

The input is given from Standard Input in the following format:

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

输入从标准输入中按以下格式给出：

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

Output the answer.

输出答案。

Sample 1 Explanation:
You are initially at town $3$. If you move in the order town $3 \to 2 \to 3 \to 4 \to 5$, the total distance traveled is $2 + 2 + 4 + 1 = 9$, and the towns visited are $2, 3, 4, 5$, that is, four towns.

It is impossible to visit five or more towns with a total travel distance of at most $10$, so the answer for this case is $4$.

Constraints

• $2 \leq N \leq 8000$
• $1 \leq S \leq N$
• $0 \leq L \leq 10^{18}$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

样例 1 解释：
你初始位于城镇 $3$。若按城镇 $3 \to 2 \to 3 \to 4 \to 5$ 的顺序移动，则总行程距离为 $2 + 2 + 4 + 1 = 9$，访问过的城镇为 $2, 3, 4, 5$，即共 $4$ 个城镇。

在总行程距离不超过 $10$ 的前提下，无法访问 $5$ 个或更多城镇，因此本例的答案为 $4$。

约束条件

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