题目描述

有 $N$ 个城镇在一条直线上排成一排，编号分别为 $1, 2, \dots, N$。对于每个满足 $1 \le i \le N-1$ 的整数 $i$，城镇 $i$ 和城镇 $i+1$ 之间有一条长度为 $A_i$ 的道路相连。

你最初位于城镇 $S$。你可以通过道路在相邻的城镇之间反复移动。

请计算：在总移动距离不超过 $L$ 的前提下，能够访问到的不同城镇的最大数量。 注意：初始所在的城镇 $S$ 也计入访问过的城镇中，且如果同一个城镇被访问了多次，它只被计算一次。

输入格式

第一行包含三个整数 $N, S, L$ —— 分别表示城镇的总数、你初始所在的城镇编号以及最大允许的总移动距离。

第二行包含 $N-1$ 个正整数 $A_1, A_2, \dots, A_{N-1}$ —— 分别表示每条道路的长度。

输出格式

输出一行，一个整数，表示在总移动距离不超过 $L$ 的情况下，最多能访问多少个不同的城镇。

样例输入 1

6 3 10
5 2 4 1 6

样例输出 1

4

样例输入 2

8 8 17
2 3 4 4 3 5 1

样例输出 2

6

样例输入 3

2 1 1000000000000000000
10000

样例输出 3

2

样例输入 4

9 6 28
5 4 9 2 3 6 1 4

样例输出 4

6

说明

样例解释

在第一个样例中，你最初在城镇 $3$。如果你按城镇 $3 \to 2 \to 3 \to 4 \to 5$ 的顺序移动，总移动距离为 $2 + 2 + 4 + 1 = 9$，这小于等于 $10$。访问过的城镇有 $2, 3, 4, 5$，共计 $4$ 个。 在总移动距离不超过 $10$ 的情况下，无法访问 $5$ 个或更多的城镇，因此该样例的答案为 $4$。

数据范围

对于所有测试点，保证：

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