Problem Statement

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.

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.

Input

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

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

Output

Output the answer.

6 3 10
5 2 4 1 6

4

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$.

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

• Source: AtCoder ABC 475 C