题目描述

本题题解已发表至 讨论区

我们有一个长度为 $N$ 的正整数序列：$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}$
- 所有数均为整数

输出描述

输出一个数$k$表示答案

示例 1

输入

3
3 5 2
26

输出

8

说明

$B=(3,5,2,3,5,2,3,5,2,\dots)$.
$\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26}$，可以发现这是第一个大于目标的位置，所以答案是 $8$.

示例 2

输入

4
12 34 56 78
1000

输出

23