Có 𝑁 gói kẹo được đánh số từ 1 đến ~𝑁~, gói thứ ~𝑖~ có số kẹo là số nguyên dương ~𝑎_𝑖~ (~1 ≤ 𝑖 ≤ 𝑁~). Vương quốc Alpha có ~𝐾~ cháu được nhận kẹo, Quốc Vương muốn chọn các gói kẹo liên tiếp nhau sao cho tổng số kẹo trong các gói có thể chia đều cho các cháu và số kẹo mỗi cháu được nhận là lớn nhất.

Yêu cầu: Xác định số kẹo nhiều nhất mà mỗi cháu có thể nhận được.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương ~𝑁~, ~𝐾~ (~1 ≤ 𝐾 ≤ 10000~);

• Dòng thứ hai ghi 𝑁 số lần lượt ~𝑎_1, 𝑎_2, … , 𝑎_𝑁~ có giá trị không quá 10000; Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Kết quả:

• Ghi ra một dòng ghi kết quả tìm được.

Ràng buộc:

• Có 50% số điểm ~10 ≤ 𝑁 ≤ 200~;

• Có 30% số điểm ~200 < 𝑁 ≤ 10000~;

• Có 20% số điểm ~10000 < 𝑁 ≤ 1000000~.

Ví dụ:

Input

6 3
1 3 3 4 5 4

Output

5

Giải thích:

• Chọn các gói {3,3,4,5} có tổng số kẹo là 15. Do đó số kẹo mỗi cháu nhận được là 5.