← 返回题目列表

Codeforces · 366/B

B. 迪玛和待办事项列表

中文机器翻译题面 查看原题

你帮助 Dima 度过了一个愉快的周末,但现在是工作时间了。当然,迪马和所有其他有女朋友的男人一样,做的每件事都是错的。

Inna 和 Dima 现在在一间房间里。伊娜责备迪玛在她面前所做的一切。伊娜因某件事斥责了他之后,她去了另一个房间,绕着圈子走到那里,嘀咕着她的爱人是多么无用。在那段时间里迪玛有时间平静地完成k-1个任务。然后伊娜回来并告诉迪玛他在她面前要做的下一个任务,然后又去了另一个房间。它会一直持续到迪马完成他的任务为止。

总的来说,迪玛有 n 个任务要做,每个任务都有一个从 1 到 n 的唯一编号。迪马喜欢秩序,所以他从某项任务开始连续执行任务。例如,如果迪马总共有6个任务要做,那么,如果他从第5个任务开始,顺序是这样的:迪马先做第5个任务,然后是第6个任务,然后是第1个任务,然后是第2个任务,然后是第3个任务,然后是第4个任务。

伊娜(Inna)如此频繁且系统地责备迪玛(只是充满爱意且恰当!),以至于他非常了解她在每项任务中责备他的力量。帮助迪马选择第一个任务,这样他就可以用尽可能小的力量被训斥。

输入

输入的第一行包含两个整数 n, k (1 ≤ k ≤ n ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 103),其中 ai 是 Inna 告诉 Dima 的权力,如果 Dima 正在执行第 i 个任务时她在房间里。

保证n能被k整除。

输出

在一行中打印 Dima 应该开始的任务编号,以便以尽可能少的功率被告知。如果有多个解决方案,则打印第一个要做的任务数量最少的解决方案。

示例

输入 #1

6 2
3 2 1 6 5 4

输出 #1

1

输入 #2

10 5
1 3 5 7 9 9 4 1 8 5

输出 #2

3

注意

第一个示例的说明。

如果 Dima 从第一个任务开始,Inna 用权力 3 告诉他,然后 Dima 可以再做一项任务(当 k = 2),然后 Inna 用权力 1 告诉他第三个任务,然后她用权力 5 告诉他第五个任务。因此,Dima 被告知总权力 3 + 1 + 5 = 9。例如,如果 Dima 从第二个任务开始,那么 Inna 会告诉他任务 2、4 和 6,功率为 2 + 6 + 4 = 12。

第二个示例的说明。

在第二个示例中,k = 5,因此,Dima 设法在训斥会话之间完成 4 项任务。因此,Inna 会告诉 Dima 任务 1 和 6(如果他从 1 或 6 开始)、2 和 7(如果他从 2 或 7 开始)等等。最佳答案是从任务3或8开始,3的数字较小,所以答案是3。