题目描述

给定一个长度为 $N$ 的序列 $A=(A_0,A_1,\\ldots,A_{N-1})$。
开始时，有一个空盘子。Takahashi 将重复进行以下操作 $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$ 次操作，我们有 $X=0$，所以盘子上将再放入 $A_{(0\\mod 5)}=A_0=2$ 颗糖果。
• 第 $2$ 次操作，我们有 $X=2$，所以盘子上将再放入 $A_{(2\\mod 5)}=A_2=6$ 颗糖果。
• 第 $3$ 次操作，我们有 $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$ 位整数类型中。