Bức ảnh đẹp

Trong một chuyến phiêu lưu tới thành phố hiện đại Lumina, cô gái Lan Anh đang đứng trước một dãy các toà nhà chọc trời rực rỡ ánh đèn. Cô quyết định chụp một bức ảnh thật đẹp để ghi lại khoảnh khắc này.

Dãy các toà nhà này có thể được mô tả bởi một dãy số gồm \(n\) toà nhà với chiều cao lần lượt là \(h_1, h_2, \dots, h_n\). Lan Anh sẽ chọn một đoạn liên tiếp của dãy toà nhà này để chụp ảnh. Tuy nhiên, để bức ảnh trở nên đáng giá, đoạn được chọn phải có ít nhất \(k\) toà nhà.

Lan Anh có một tiêu chí rất đặc biệt để đánh giá vẻ đẹp của một bức ảnh: cô thích những toà nhà cao, và còn thích hơn nếu chiều cao của các toà nhà có ước chung lớn! Cụ thể, nếu cô chọn một đoạn từ \(h_l\) đến \(h_r\), gọi \(g\) là ước số chung lớn nhất (GCD) của các chiều cao trong đoạn đó, thì vẻ đẹp của bức ảnh được tính bằng:

Bạn hãy giúp Lan Anh tính ra giá trị vẻ đẹp lớn nhất mà cô ấy có thể đạt được với một bức ảnh chụp ít nhất \(k\) toà nhà liên tiếp.

Input

\begin itemize

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n, k \le 10^6\)).

• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(1 \le h_i \le 10^6\)).
  \end itemize

Output

In ra một số nguyên --- vẻ đẹp lớn nhất có thể đạt được.

Example

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

Scoring

• Subtask 1 (11 điểm): \(n, k \le 100\)
• Subtask 2 (28 điểm): \(n, k \le 5000\)
• Subtask 3 (18 điểm): \(h_i \le 100\)
• Subtask 4 (17 điểm): \(n, k \le 5 \cdot 10^4\)
• Subtask 5 (26 điểm): Không có ràng buộc thêm