分数: 500 点
问题陈述
给你一个序列 A=(A_0,A_1,\ldots,A_{N-1}) 长度 N.
有一个最初是空的盘子。 高桥将重复以下操作 K 次。
- 让 X 是盘子上糖果的数量。 他把 A_{(X\bmod N)} 盘子里有更多糖果。 在这里, X\bmod N 表示当 X 除以 N.
找出盘子上有多少糖果 K 操作。
约束
- 2 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^{12}
- 1 \leq A_i\leq 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
A_0 A_1 \ldots A_{N-1}
输出
打印答案。
示例输入 1
5 3 2 1 6 3 1
示例输出 1
11
盘子上的糖果数量变化如下。
- 在 1-st 操作,我们有 X=0,所以 A_{(0\mod 5)}=A_0=2 盘子里会放更多糖果。
- 在 2-nd操作,我们有 X=2,所以 A_{(2\mod 5)}=A_2=6 盘子里会放更多糖果。
- 在 3-rd操作,我们有 X=8,所以 A_{(8\mod 5)}=A_3=3 盘子里会放更多糖果。
因此,之后 3 操作时,会有 11 盘子里有糖果。 请注意,您必须 不 打印除以的余数 N.
示例输入 2
10 1000000000000 260522 914575 436426 979445 648772 690081 933447 190629 703497 47202
示例输出 2
826617499998784056
答案可能不适合 32- 位整数类型。