Description

小明和小花在研究重复序列了。
给定一个有 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 + ... + bk > X 的最小 k 值。

Input Format

输入第一行是一个正整数 N，表示 a 序列的正整数个数。
输入第二行是有 N 个正整数组成，空格隔开。
输入第三行是一个正整数 X。

Output Format

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

2
1 2
5

4

Hint

【输入输出样例 1】

seq.in	seq.out
2 1 2 5	4

b 序列为 1,2,1,2,1,2...，前 4 个数的和是 6，超过了 X = 5，所以 k 最小是 4。

【输入输出样例 2】

seq.in	seq.out
3 3 5 2 26	8

这里，构成的 b 序列是 3,5,2,3,5,2,3,5,2,...，前 8 个数的和是 28，超过了 X = 26。

【输入输出样例 3】

seq.in	seq.out
4 12 34 56 78 1000	23

这里，构成的 b 序列是 3,5,2,3,5,2,3,5,2,...，前 8 个数的和是 28，超过了 X = 26。

【数据范围】
对于所有的数据：1 ≤ N ≤ 10^5, 1 ≤ ai ≤ 10^18, 1 ≤ X ≤ 10^30。

Source

字符串