#T168. 月读环形音轨

月读环形音轨

题目描述

在虚拟空间“月读”中,辉夜与彩叶正在准备一场特别的演出。舞台的音轨由 nn 个首尾相连的音符节点组成,按照播放方向编号为 1,2,…,n1,2,\ldots,n。从节点 nn 继续向前,会回到节点 11。

辉夜在月读中准备演出

第 ii 个节点的应援能量变化为 aia_i。能量变化可能是负数,表示该节点受到了干扰,会消耗已经积累的应援能量。

辉夜要选择一个节点作为演出的起点,然后按照播放方向依次经过恰好 kk 个节点,起点本身也计算在内。经过的节点可以越过编号 nn,从编号 11 继续。例如,当 n=6n=6、k=3k=3、起点为 55 时,经过的节点依次为 5,6,15,6,1。

请你帮助彩叶计算演出能够获得的最大应援能量总和。如果有多个起点都能得到最大总和,请选择编号最小的起点。

输入格式

第一行包含两个整数 nn 和 kk,分别表示音符节点的数量和演出需要经过的节点数量。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示第 ii 个节点的应援能量变化。

输出格式

输出两个整数:最大应援能量总和,以及取得该最大值的最小起点编号。两个整数之间用一个空格分隔。

数据范围

  • 1≤k≤n≤2×1051 \le k \le n \le 2\times 10^5;
  • −109≤ai≤109-10^9 \le a_i \le 10^9;
  • 所有输入均为整数。

答案可能超出 32 位有符号整数的范围。

提示

辉夜的提示

让你们乱点,训练结束了吗就点。

样例 1

6 3
4 -2 3 1 -5 6
8 6

样例 1 解释

从节点 66 出发时,依次经过节点 6,1,26,1,2,应援能量总和为 6+4−2=86+4-2=8。

样例 2

4 2
2 -2 2 -2
0 1

样例 2 解释

四个起点得到的应援能量总和都为 00,因此选择编号最小的起点 11。

样例 3

5 1
-7 -3 -3 -5 -4
-3 2