Mã hoá

Cho dãy $N$ số nguyên dương $A_1,A_2,\dots ,A_N$ và một số nguyên dương $p$.

Định nghĩa điểm của một dãy con là tổng các phần tử của nó lấy dư cho $p$.

Bạn cần chia dãy $A$ thành đúng $2$ phần sao cho:

• Mỗi phần gồm các phần tử liên tiếp của $A$;
• Mỗi phần chứa ít nhất một phần tử;
• Hai phần không giao nhau và hợp lại tạo thành toàn bộ dãy $A$.

Nói cách khác, bạn chọn một vị trí cắt $i$ với $1\le i\le N-1$, phần thứ nhất là $A_1,\dots ,A_i$ và phần thứ hai là $A_{i+1},\dots ,A_N$.

Hãy tìm giá trị lớn nhất của tổng điểm hai phần.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $p$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$.

Dữ liệu ra

Một số nguyên duy nhất là tổng điểm lớn nhất tìm được.

Ràng buộc

• $2\le N\le 100000$
• $2\le p\le 10000$
• $1\le A_i\le 1000000$

Ví dụ