We have a sequence of $N$ positive integers: $A=(A_1,\dots,A_N)$. Let $B$ be the concatenation of $10^{100}$ copies of $A$. Consider summing up the terms of $B$ from left to right. When does the sum exceed $X$ for the first time? In other words, find the minimum integer $k$ such that: $\displaystyle{\sum_{i=1}^{k} B_i \gt X}$.

Input is given from Standard Input in the following format: >$N$ >$A_1$ $\ldots$ $A_N$ >$X$ #### Constraints - $1 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq X \leq 10^{18}$ - All values in input are integers.

Print the answer.

AtCoder [ABC220C]