题目描述

我们有一个长度为 $N$ 的正整数序列：$A=(A_1,\dots,A_N)$。

定义 $B$ 为 $A$ 重复 $10^{100}$ 次的连接。考虑从左到右对 $B$ 的项进行求和。第一次和超过 $X$ 是在什么时候？

换句话说，找到最小的整数 k，使得：$\displaystyle{\sum_{i=1}^{k}\ B_i\ \gt\ X}$。

输入格式

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

$N$

$A_1$ $\ldots$ $A_N$

$X$

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

3
3 5 2
26

输出 #1

8

输入输出样例 #2

输入 #2

4
12 34 56 78
1000

输出 #2

23

说明/提示

样例 1 解释

我们有 $B=(3,5,2,3,5,2,3,5,2,\cdots)$。

$\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}$
• 输入中的所有值都是整数。