P9032 [COCI 2022/2023 #1] Neboderi

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

这排摩天大楼共有 $n$ 座，它们可以被视作序列 $h_1,h_2,...h_n$，其中 $h_i$ 为第 $i$ 栋楼的高度。Domagoj 将会拍下这排大楼的一个子区间。为了更好地捕捉城市之美，他想拍摄至少 $k$ 座摩天大楼。 Domagoj 有着奇怪的审美：他认为照片中有高大的摩天大楼是美的；但如果照片中所有的摩天大楼的高度有着很大的公因数，他会认为更美。 如果一张照片拍下的大楼区间为 $[l,r]$，且这段区间内所有大楼高度的 $\gcd$ 为 $g$，则 Domagoj 定义这张照片的“美丽度”为 $g \times \sum_{i=l}^r h_i$。 帮助 Domagoj 算出他能拍到的最美照片的美丽度吧！

第一行包含两个整数 $n,k$，分别表示大楼总数和 Domagoj 至少拍到的大楼数。 第二行包含 $n$ 个整数 $h_i$，依次表示每座大楼的高度。

一行一个整数，即最大美丽值。

| 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $11$ | $n,k \leq 100$ | | $2$ | $22$ | $n,k \leq 5000$ | | $3$ | $27$ | $k \leq 100$ | | $4$ | $18$ | $n,k \leq 5\times 10^4$ | | $5$ | $32$ | 无特殊性质 | 对于 $100\%$ 的数据，满足 $1\leq k \leq n \leq 10^6,1\leq h_i \leq 10^6$。 本题满分 $110$ 分。