题目背景

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$，依次表示每座大楼的高度。

输出格式

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

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

提示

对于 $100\%$ 的数据，满足 $1\leq k \leq n \leq 10^6,1\leq h_i \leq 10^6$。

本题满分 $110$ 分。