文件读写

输入文件：travel.in

输出文件：travel.out

题目描述

有 $N$ 个城镇排在一条直线上，编号为 $1,2,\ldots,N$。城镇 $i$ 与城镇 $i+1$ 之间有一条长度为 $A_i$ 的道路。

你从城镇 $S$ 出发，可以沿道路在相邻城镇之间移动。在总移动距离不超过 $L$ 的前提下，最多能访问多少个不同的城镇？

起点 $S$ 也计入访问过的城镇。同一个城镇访问多次只计算一次；每次经过一条道路都要计算其长度。最后可以停在任意城镇。

输入格式

第一行三个整数 $N,S,L$。

第二行 $N-1$ 个整数 $A_1,A_2,\ldots,A_{N-1}$。

输出格式

输出一个整数，表示最多能访问的不同城镇数量。

样例 1

6 3 10
5 2 4 1 6

4

按 $3\to2\to3\to4\to5$ 的顺序移动，总距离为 $9$，访问了四个不同的城镇。

样例 2

8 8 17
2 3 4 4 3 5 1

6

样例 3

2 1 1000000000000000000
10000

2

样例 4

9 6 28
5 4 9 2 3 6 1 4

6

数据范围

对于所有测试数据，$2\le N\le8000$，$1\le S\le N$，$0\le L\le10^{18}$，$1\le A_i\le10^9$。所有输入值均为整数。