AT_abc475_c [ABC475C] 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.

The input is given from Standard Input in the following format: > $ N $ $ S $ $ L $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_{N - 1} $

Output the answer.

### Sample Explanation 1 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.