题目描述

探险队进入了一个神秘地宫，里面有n堆宝石，每堆宝石个数为正整数。取宝石规则如下：探险者需要选定一堆宝石作为起点，从该堆开始每隔k堆宝石拿一堆宝石，求探险队最多能拿走多少个宝石？

输入描述

第一行：两个正整数n、k，用一个空格隔开； 第二行：n个正整数 a₁,a₂,…,aₙ，表示每堆宝石的个数。

输出描述

一个整数，表示最多能拿走的宝石个数。

样例1

输入

7 2
4 6 2 1 10 1 3

输出

16

提示

样例说明

• 从第1堆开始拿：拿走第1、4、7堆，总和为4+1+3=8
• 从第2堆开始拿：拿走第2、5堆，总和为6+10=16
• 从第3堆开始拿：拿走第3、6堆，总和为2+1=3
• 从第4堆开始拿：拿走第4、7堆，总和为1+3=4
• 从第5堆开始拿：拿走第5堆，总和为10
• 从第6堆开始拿：拿走第6堆，总和为1
• 从第7堆开始拿：拿走第7堆，总和为3

数据范围

• 60% 的数据：1 ≤ n ≤ 10³，1 ≤ k ≤ 10³，且k不超过100，每堆宝石个数不超过10⁵。
• 60% 数据解法：枚举n个位置，每k个选一个计算总和，求最大值，时间复杂度O(n²/k)。
• 100% 数据解法：通过递推优化或分组后缀和实现线性时间复杂度，时间复杂度O(n)。