C問題 - Colorful Note

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

C君は色\(i\)のノートを\(A_i \quad (1 \leq i \leq N)\)冊持っています。

しかしC君は目が悪いので、ある自然数\(j\)が存在して、\(j \% N + 1, (j + 1) \% N + 1, \cdots ,(j+k-1)\% N + 1\)の色のノートしかノートと認識できません。

C君がノートと認識できる冊数が最大となるような\(j\)の最小値とそのときの認識できる冊数\(S\)を出力してください。

ただし、自然数\(n,m\)に対して\(n \% m\)は「\(n\)を\(m\)で割った余り」を表します。

制約

• \(1 \leq k \leq N \leq 2 \times 10^5\)
• \(0 \leq A_i \leq 10^9\)
• 入力はすべて整数で与えられる。

入力

N k
A_1 A_2 ... A_N

出力

j S

• \(j\)の最小値とそのときの認識できるノートの冊数\(S\)を上記のように1行に出力せよ。

入力例1

5 2
1 2 3 4 5

出力例1

4 9

\(j=4\)とすることで、C君は色4のノート4冊と色5のノート5冊の合計9冊を認識できます。

入力例2

4 1
114 514 1919 810

出力例2

3 1919

ノートを1色しか認識できないC君も存在します。

入力例3

10 10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例3

1 10000000000

出力が32bit整数型に収まらない場合があります。また\(S\)が最大となる\(j\)が複数存在するときはその最小値を出力する必要があることに注意してください。