Trong một cánh đồng dài có ~n~ thửa ruộng nằm liền kề nhau. Mỗi thửa ruộng có năng suất thu hoạch lần lượt là ~a_i, a_2, ..., a_n~, trong đó ~a_i~ là số kg lúa thu được trên thửa ruộng thứ ~i~.

Một nông dân muốn thu hoạch một đoạn ruộng liên tiếp để thuận tiện cho việc vận chuyển và đóng gói. Để việc thu hoạch hiệu quả hơn, ông muốn chọn một đoạn gồm ít nhất ~k~ thửa ruộng liên tiếp.

Giả sử người nông dân chọn đoạn ruộng từ thửa ~l~ đến ~r~ (~l \le r~) Khi đó:

- Tổng sản lượng lúa thu được là: ~a_l + a_{l+1} + ... + a_r~.

- Gọi ~g~ là ước số chung lớn nhất (GCD) của các giá trị ~a_l, a_{l+1}, ..., a_r~.

Hiệu quả thu hoạch của đoạn ruộng được định nghĩa là:

Hiệu quả = ~g*(a_l+a_{l+1}+...+a_r)~

Nhiệm vụ của bạn là xác định đoạn ruộng gồm ít nhất ~k~ thửa ruộng liên tiếp sao cho hiệu quả thu hoạch là lớn nhất.

Input

- Dòng thứ nhất chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^6~) - số thửa ruộng và số thửa tối thiểu cần chọn.

- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6~) - năng suất thu hoạch của mỗi thửa ruộng.

Output

In ra một số nguyên duy nhất là hiệu quả thu hoạch lớn nhất có thể đạt được.

Scoring

+ ~10\%~ số điểm tương ứng với ~n, k \le 100~.

+ ~20\%~ số điểm tương ứng với ~n, k \le 5*10^3~.

+ ~30\%~ số điểm tương ứng với ~n, k \le 5*10^4~.

+ ~40\%~ số điểm không có ràng buộc thêm.

Sample Input 1

7 2
1 2 1 4 4 4 2

Sample Output 1

48