题目描述

我们有一个正整数序列 $A=(A_1,\\dots,A_N)$。
令 $B$ 为重复 $10^{100}$ 个 $A$ 的串联。

考虑从左到右对 $B$ 的项进行求和。第一次求和超过 $X$ 是在什么时候？
换句话说，找到最小的整数 $k$，使得：

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

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq X \leq 10^{18}$
• 输入中的所有值都是整数。

输入

从标准输入中按照以下格式给出输入：

$N$ $A_1$ $\\ldots$ $A_N$ $X$

输出

打印答案。

示例输入 1

3
3 5 2
26

示例输出 1

8

我们有 $B=(3,5,2,3,5,2,3,5,2,\\dots)$。
当 $k$ 是 $8$ 时，$\\displaystyle{\\sum_{i=1}^{8} B_i = 28 \\gt 26}$ 成立，但当 $k$ 小于等于 $7$ 时，不满足条件，因此答案是 $8$。

示例输入 2

4
12 34 56 78
1000

示例输出 2

23