题目描述

小明和小花在研究重复序列了。

给定一个有 $N$ 个正整数组成的序列 $a_1, a_2,....a_n$，然后我们可以把这个序列重复无限次，然后依次摆放，就变成了 $a_1,a_2,....a_n$，$a_1,a_2,....a_n$，$a_1,a_2,....a_n$，这些无穷的重复序列构成了一个新的序列 $b$，即 $b_1=a_1$，$b_2=a_2$，……，$b_n=a_n$，$b_{n+1}=a_1$，$b_{n+2}=a_2$，......，$b_{2n}=a_n$，......

现在，小明希望求出满足下列条件的最小的 $k$：

使得 $b_1＋b_2＋b_3+...+b_k>X$

输入格式

输入第一行是一个正整数 $N$，表示 $a$ 序列的正整数个数。

输入第二行是有 $N$ 个正整数组成，空格隔开。

输入第三行是一个正整数 $X$。

输出格式

输出满足条件的最小的 $k$ 值。

2	
1  2
5

4

3	
3  5  2
26

8

4
12  34  56  78
1000

23

数据范围

对于所有数据：$1 \le N \le 10^5$，$1 \le a_i \le 10^{18}$，$1 \le X \le 10^{30}$

其中 $20\%$ 的数据，$N \le 10^5$，$a_i \le 10$，$X \le 10^3$

其中 $50\%$ 的数据，$N \le 10^5$，$a_i \le 10^9$，$X \le 10^{18}$

其中 $30\%$ 的数据，$N \le 10^5$，$a_i<=10^{18}$，$X \le 10^{30}$，并保证 $a_i$ 和 $X$ 都是 $10^{12}$ 的正整数倍