题目描述

小明和小花在研究重复序列了。
给定一个有 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 值

输入格式

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

输出格式

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

样例数据1

input

2
1 2
5

output

4

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

样例数据2

input

3
3 5 2
26

output

8

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

样例数据3

input

4
12 34 56 78
1000

output

23

数据范围

对于所有的数据：1 ≤ N ≤ 10^5, 1 ≤ ai ≤ 10^18, 1 ≤ X ≤ 10^30。
数据编号    数据范围                     特殊性质
1∼2        N ≤ 10^2, ai ≤ 10, X ≤ 10^3     所有的 ai 都是相同的
3∼7     N ≤ 10^5, ai ≤ 10^9, X ≤ 10^18     无 
8∼10     N ≤ 10^5, ai ≤ 10^18, X ≤ 10^30     保证 ai 和 X 都是 10^12 的正整数倍