레이팅 미적용Domagoj is in the big city of London! Right now, there is a sequence of tall
skyscrapers in front of him and he wants to take a photograph to remember the
moment.
The sequence of skyscrapers can be represented as a sequence of \(n\) numbers
\(h_{1}\), \(h_{2}\), . . . , \(h_{n}\) where the number \(h_{i}\) represents the height of the \(i\)-th skyscraper.
Domagoj will photograph a contiguous subsequence of skyscrapers. To capture
more of the city’s beauty, he wants to photograph at least \(k\) skyscrapers.
Domagoj has a strange sense of beauty of a photograph. He is very happy when there are tall skyscrapers
in the photograph, but he is even happier when their heights have a large common divisor! If we label the
heights of the contiguous skyscrapers on the photograph with \(h_{l}\), . . . , \(h_{r}\), and with \(g\) the greatest common
divisor of the selected heights, then Domagoj defines the beauty of the photograph as \(g\) · (\(h_{l}\) + . . . + \(h_{r}\)).
Help Domagoj determine the beauty of the most beautiful photograph with at least \(k\) skyscrapers!
The first line contains two integers \(n\), \(k\) (\(1 \le k \le n \le 10^{6}\)), the number of skyscrapers, and the number \(k\).
The second line contains \(n\) integers \(h_{1}\), \(h_{2}\), . . . , \(h_{n}\) (\(1 \le h_{i} \le 10^{6}\)), the heights of the skyscrapers, in order.
Print a single line with the required number from the task.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 11점 | n, \(k \le 100\) |
2 | 22점 | n, \(k \le 5000\) |
3 | 27점 | \(h_{i} \le 100\) |
4 | 18점 | n, \(k \le 5 \cdot 10^{4}\) |
5 | 32점 | No additional constraints. |
6 2
2 1 4 4 4 2484 1
7 3 9 481Clarification of the first example:
Domagoj photographed skyscrapers ( 4, 4, 4 ), so the total beauty is 4 · (4 + 4 + 4) = 48
Clarification of the second example:
Domagoj photographed only the skyscraper ( 9 ), so the total beauty is 9 · 9 = 81.