题目描述

我们有一个长度为 $N$ 的正整数序列：$A=(A_1,\ldots,A_N)$。
定义 $B$ 为 $A$ 重复 $10^{100}$ 次的连接。考虑从左到右对 B 的项进行求和。第一次和超过 X 是在什么时候？
换句话说，找到最小的整数 k，使得：$\sum_{i=1}^{k} B_i > X$。

输入格式

输入从标准输入中以下列格式给出：
$N$
$A_1$ $\ldots$ $A_N$
$X$

输出格式

输出所求答案。

样例

3
3 5 2
26

8

4
12 34 56 78
1000

23

样例1解释

我们有 $B=(3,5,2,3,5,2,3,5,2,…)$。
$\sum_{i=1}^{8} B_i = 28 > 26$ 成立，但当 k 为 7 或更小时条件不满足，所以答案是 8。

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq X \leq 10^{18}$

输入中的所有值都是整数。

来源

• AtCoder ABC220C