Background

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

给定一个有N个正整数组成的序列a1, a2,....an，然后我们可以把这个序列重复无限次，然后依次摆放，就变成了a1, a2,....an，a1, a2,....an，a1, a2,....an，这些无穷的重复序列构成了一个新的序列b，即b1=a1, b2= a2，……,bn=an，bn+1=a1，bn+2=a2，...，b2n=an,.........

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

使得b1＋b2＋b3...+ bk > X

Input

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

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

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

Output

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

Samples

2	
1  2
5

4

3	
3  5  2
26

8

4
12  34  56  78
1000

23

Limitation

对于所有数据：1<=N<=10^5，1<=ai<=10^18，1<=X<=10^30

其中20%的数据，N<=10^5，ai<=10，X<=10^3

其中50%的数据，N<=10^5，ai<=10^9，X<=10^18

其中30%的数据，N<=10^5，ai<=10^18，X<=10^30，并保证ai和X都是10^12的正整数倍