题目描述

译自 COCI 2022/2023 Contest #1 T5「Neboderi」

Dornagoj 目前在大城市伦敦！现在，在他面前有一排摩天大楼，他想要拍摄照片纪念这个时刻。

这排摩天大楼可以用一个 $n$ 个数的序列 $h_1, h_2, \ldots, h_n$ 表示，其中 $h_i$ 表示第 $i$ 座楼的高度。Dornagoj 将拍摄连续的一段摩天楼。为了把城市拍得更美，他想要拍下来至少 $k$ 座楼。

Dornagoj 对照片有一种奇怪的审美。当照片中有摩天大楼时他会很高兴，但当这些楼的高度有大的公共因子时他会更高兴。如果我们用 $h_1, h_2, \ldots, h_m$ 表示照片中拍下的这段连续的摩天楼的高度，用 $g$ 表示这些楼高度的最大公约数的话，Dornagoj 定义这张照片的美观度为 $g \cdot (h_1 + \ldots + h_m)$。

请帮 Dornagoj 确定拍下来至少 $k$ 座楼的情况下照片的最大美观度。

输入格式

第一行两个整数 $n, k$ ($1 \le k \le n \le 10^6$)，表示摩天大楼数。

第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^6$)，按顺序表示这些楼的高度。

输出格式

输出一行一个整数表示答案。

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

数据规模与约定

对于 $100$ 的数据，$1 \le k \le n \le 10^6$，$1 \le h_i \le 10^6$。