Cho dãy \(n\) số nguyên \(a_1, a_2, …, a_n\) và một số nguyên \(k\). Mức độ đẹp của một dãy con liên tiếp \(a_i, a_{i+1}, …, a_j\) được đánh giá bằng \(GCD(a_i, a_{i+1}, …, a_j).(a_i + a_{i+1} + … + a_j)\), tức là độ đẹp bằng ước chung lớn nhất của các phần tử trong dãy con nhân với tổng các phần tử trong dãy con đó.

Yêu cầu: Tìm dãy con liên tiếp có ít nhất \(k\) phần tử và có mức độ đẹp là lớn nhất.

Input

• Dòng 1: Hai số nguyên \(n, k\ (1 ≤ k ≤ n ≤ 10^6)\);
• Dòng 2: \(n\) số nguyên \(a_1, a_2, …, a_n\ (1 ≤ a_i ≤ 10^6)\).

Output

• Ghi ra một số nguyên duy nhất là mức độ đẹp tìm được.

Scoring

• 10% số điểm tương ứng với 10% số test có \(n, k ≤ 100\);
• 20% số điểm tương ứng với 20% số test có \(n, k ≤ 5000\);
• 25% số điểm tương ứng với 25% số test có \(a_i ≤ 100\);
• 20% số điểm tương ứng với 20% số test có \(n, k ≤ 5.10^4\);
• 25% số điểm tương ứng với 25% số test không có ràng buộc gì thêm

Example

6 2
4 4 4 3 1 3            

48