最美天际线（skyline）

时空限制：1s/512M，测试数据共 10 组

问题描述

上海，也被称为魔都，因为魔幻渗透到了这座城市的每个角落。其中，最显而易见的魔幻之处，肯定就是上海高楼大厦组成的天际线。面对如此大规模的高楼，要想拍出最美天际线的好照片可不太容易。为了研究这个问题，我们假设有 $n$ 幢大楼一字排开，从左到右编号依次为 $1$ 到 $n$。第 $i$ 幢大楼的高度为 $h[i]$。现在要选取其中连续一段高楼拍摄进照片里。以下为分析照片所需要的一些定义：

1. 定义照片中高楼的壮观程度为这些大楼的总高度，即 $S = \sum_{i=l}^{r} h[i]$，其中 $l$ 和 $r$ 是拍摄的高楼的起始和结束位置。
2. 定义照片中高楼的相关程度为这些大楼高度的最大公约数，即 $\text{gcd}(h[l], h[l+1], \ldots, h[r])$。
3. 定义照片的美妙程度为照片中高楼的壮观程度乘以相关程度，即 $M = S \cdot \text{gcd}(h[l], h[l+1], \ldots, h[r])$。

对于给定的大楼信息，请设计最优的照片拍摄方案。要求拍摄的照片里至少包含 $k$ 幢大楼。请问，能拍出照片的最大美妙程度是多少？

输入格式

输入第一行为正整数 $n$ 和 $k$。第二行为 $n$ 个正整数，代表长度为 $n$ 的正整数序列，第 $i$ 个数为 $h[i]$。

输出格式

输出一个整数。

样例 1 输入

6 2
2 1 4 4 4 2

样例 1 输出

48

样例 1 解释

选择 $4, 4, 4$，总和为 $12$，最大公约数为 $4$，答案为 $12 \cdot 4 = 48$。

样例 2 输入

4 1
7 3 9 4

样例 2 输出

81

样例 2 解释

选择 $9$，总和为 $9$，最大公约数为 $9$，答案为 $9 \cdot 9 = 81$。

数据规模与约定

测试点编号: 特殊性质

1~2: $1 \leq k \leq n \leq 5000$

3~4: 所有 $h[i] \leq 100$

5~10: 无

对于所有数据：$1 \leq k \leq n \leq 1000000$，所有 $h[i] \leq 1000000$