题目描述

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

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

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

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

请帮 Domagoj 确定拍下来至少 $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

数据范围与提示

详细子任务附加限制及分值如下表所示。