COCI '22 Contest 1 #5 Neboderi

Points: 15 (partial)

Time limit: 2.5s

Memory limit: 512M

Problem type

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$ ~n~ numbers $h_1, h_2, \dots, h_n$ ~h_1, h_2, \dots, h_n~ where the number $h_i$ ~h_i~ represents the height of the $i$ ~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$ ~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, \dots, h_r$ ~h_l, \dots, h_r~, and with $g$ ~g~ the greatest common divisor of the selected heights, then Domagoj defines the beauty of the photograph as $g \cdot (h_l + \dots + h_r)$ ~g \cdot (h_l + \dots + h_r)~.

Help Domagoj determine the beauty of the most beautiful photograph with at least $k$ ~k~ skyscrapers!

Input Specification

The first line contains two integers $n, k$ ~n, k~ $(1 \le k \le n \le 10^6)$ ~(1 \le k \le n \le 10^6)~, the number of skyscrapers, and the number $k$ ~k~.

The second line contains $n$ ~n~ integers $h_1, h_2, \dots, h_n$ ~h_1, h_2, \dots, h_n~ $(1 \le h_i \le 10^6)$ ~(1 \le h_i \le 10^6)~, the heights of the skyscrapers, in order.

Output Specification

Print a single line with the required number from the task.

Constraints

Subtask	Points	Constraints
$1$ ~1~	$11$ ~11~	$n, k \le 100$ ~n, k \le 100~
$2$ ~2~	$22$ ~22~	$n, k \le 5\,000$ ~n, k \le 5\,000~
$3$ ~3~	$27$ ~27~	$h_i \le 1\,000$ ~h_i \le 1\,000~
$4$ ~4~	$18$ ~18~	$n, k \le 5 \cdot 10^4$ ~n, k \le 5 \cdot 10^4~
$5$ ~5~	$32$ ~32~	No additional constraints.