题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,\dots,A_N)$。将序列 $A$ 重复连接 $10^{100}$ 次得到新序列 $B$。

当按顺序累加 $B$ 的元素时，求首次使累加和超过 $X$ 所需的项数 $k$。即求满足以下条件的最小整数 $k$：

$\displaystyle{\sum_{i=1}^{k}\ B_i\ >\ X}$

输入格式

输入格式如下：

$N$

$A_{1}$ $A_{2}$ $\dots$ $A_N$

$X$

输出格式

输出所求的项数 $k$。

输入输出样例

样例1输入

3
3 5 2
26

样例1输出：

8

样例2输入

4
12 34 56 78
1000

样例2输出：

23

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq X \leq 10^{18}$
• 所有输入均为整数

样例1说明：

$B=(3,5,2,3,5,2,3,5,2,\dots)$。前8项和为 $28 > 26$，而前 $7$ 项和不满足条件，因此答案为 $8$。

（解题提示：可利用序列$A$的周期性特征，通过计算完整周期次数和剩余项数来优化计算）