Background

Domagoj has arrived in the big city of London! Now there is a row of tall skyscrapers in front of him, and he wants to take a photo to remember this moment.

Problem Description

There are $n$ skyscrapers in this row. They can be seen as a sequence $h_1,h_2,\ldots,h_n$, where $h_i$ is the height of the $i$-th building. Domagoj will take a photo of a subarray of these buildings. To better capture the beauty of the city, he wants to photograph at least $k$ skyscrapers.

Domagoj has a strange sense of aesthetics: he thinks that having tall skyscrapers in the photo is beautiful; but if the heights of all skyscrapers in the photo have a large common divisor, he thinks it is even more beautiful.

If a photo covers the building interval $[l,r]$, and the $\gcd$ of all building heights in this interval is $g$, then Domagoj defines the “beauty value” of this photo as $g \times \sum_{i=l}^r h_i$.

Help Domagoj compute the maximum beauty value among all photos he can take.

Input Format

The first line contains two integers $n,k$, representing the total number of buildings and the minimum number of buildings Domagoj wants to photograph.

The second line contains $n$ integers $h_i$, in order, representing the height of each building.

Output Format

Output one integer in one line, the maximum beauty value.

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

Hint

For $100\%$ of the testdata, $1\leq k \leq n \leq 10^6$ and $1\leq h_i \leq 10^6$.

The full score for this problem is $110$ points.

Translated by ChatGPT 5