累加周期

轮休完了，但Zero的系统有周期——需要累加。

"周期？"CC问。

"对。"你说，"一个序列，每$k$个数为一个周期。求前$n$项的和。"

"周期？"

"对。"你说，"每$k$个数重复一次——$a_1,a_2,\dots,a_k,a_1,a_2,\dots$"

"累加？"

"对。"你说，"求$\sum_{i=1}^n a_i$。"

"咋算？"

"整周期+余数。"你说，"先算一个周期的和，然后乘周期数，再加上剩余项。"

"$O(k)$？"

"对。"你说，"预处理周期和，然后$O(1)$回答。"

"第47项。"你说，"如果$k=10$，$47=4\times 10+7$，累加4个周期加前7项。"

"模运算？"

"对。"你说，"$47\bmod 10=7$——余数是7。"

"如果$n$很大？"

"一样。"你说，"只要知道周期，多大都能算。"

"像日历？"

"对。"你说，"像日历——星期一到星期日，周而复始。"

"第47天是星期几？"

"$47\bmod 7=5$。"你说，"如果第一天是星期一，第47天是星期五。"

"对。"

"周期让生活有规律。"你说，"知道周期，就能预测未来。"

"未来？"

"对。"你说，"第100项、第1000项——都能算。"

CC看着周期表——像一张日历，像一张课表，像某种重复的美。

"重复好？"她问。

"看情况。"你说，"好的周期给人安全感；坏的周期让人厌倦。"

"我们的周期好？"

"对。"你说，"我们在进步——每个周期都比上一个好。"

Echo把周期函数投射出来——像波浪，像心跳，像某种永恒的韵律。

"以前我乱。"她说，"现在……有规律了。"

"因为你找到了节奏。"你说。

"对。"她说，"因为我找到了节奏。

题目描述

给定周期序列，周期为$k$。求前$n$项的和。

输入格式

第一行$k$和$n$。第二行$k$个数表示一个周期。

输出格式

前$n$项的和。

输入样例

5
1 2 3 4 5

输出样例

0

提示

• 预处理周期和$S=a_1+\dots+a_k$。
• 答案$=\lfloor n/k\rfloor\times S+\sum_{i=1}^{n\bmod k}a_i$。
• 时间复杂度$O(k)$。