Có \(N\) gói kẹo được đánh số từ \(1\) đến \(N\), gói thứ \(i\) có số kẹo là số nguyên dương \(a_i\) (\(1 \le i \le N\)). Vương quốc Alpha có \(K\) 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.

Input

• Dòng đầu ghi hai số nguyên dương \(N, K\) (\(1 \le K \le 10^4\)).
• Dòng thứ hai ghi \(N\) số lần lượt \(a_1, a_2, \dots, a_N\) có giá trị không quá \(10^4\).
• Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Output

• Ghi ra một dòng duy nhất là kết quả tìm được.

Example

6 3
1 3 3 4 5 4

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(10 \le N \le 200\).
• Subtask \(2\) (\(30\%\) số điểm): \(200 < N \le 10^4\).
• Subtask \(3\) (\(20\%\) số điểm): \(10^4 < N \le 10^6\).