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.