Bài 3: Chia kẹo (5.0 điểm)

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 một đoạn các gói kẹo liên tiếp sao cho tổng số kẹo trong đoạn đó có thể chia đều cho \(K\) cháu và số kẹo mỗi cháu nhận được 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

Đọc từ tệp CAU3.INP:

• Dòng đầu tiên ghi hai số nguyên dương \(N, K\) \((1 \le K \le 10000)\);
• Dòng thứ hai ghi \(N\) số lần lượt \(a_1, a_2, \ldots, a_N\) \((a_i \le 10000)\).

Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra tệp CAU3.OUT một dòng là kết quả tìm được.

Input

%
6 3
1 3 3 4 5 4

Output

%
5

Notes

s
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\).

Scoring

• Subtask 1 (60%): \(10 \le N \le 200\).
• Subtask 2 (20%): \(200 \le N \le 10000\).
• Subtask 3 (20%): \(10000 \le N \le 1000000\).