Thực Đơn Thảm Hoạ

Sau khi nghịch ngợm trong căn nhà gỗ, Masha quyết định tự tay nấu một nồi cháo hồng siêu to khổng lồ để chiêu đãi các bạn thú trong rừng. Tuy nhiên, do cho quá tay nguyên liệu, nồi cháo bắt đầu trào ra khắp nơi.

Có \(N\) chiếc hũ chứa cháo được xếp thành một hàng ngang từ trái sang phải. Hũ thứ \(i\) hiện đang chứa \(A_i\) lít cháo.

Masha muốn chọn ra một đoạn các hũ liên tiếp từ vị trí \(L\) đến \(R\) (\(1 \le L \le R \le N\)) để đem đi phát cho các bạn. Chú Gấu đưa ra hai điều kiện an toàn nghiêm ngặt:

1. Tổng lượng cháo trong đoạn hũ được chọn phải chia hết cho \(K\) (để có thể chia đều vào \(K\) chiếc thùng chứa).
2. Đoạn hũ \([L, R]\) được chọn phải có tổng lượng cháo là lớn nhất có thể để dọn bớt cháo trào ra sàn.

Hãy giúp Chú Gấu tính tổng lượng cháo lớn nhất của một đoạn hũ liên tiếp thỏa mãn tổng chia hết cho \(K\). Nếu không tồn tại đoạn nào thỏa mãn, in ra 0.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le 100\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) lần lượt là lượng cháo trong mỗi hũ.

Output

• In ra một số nguyên duy nhất là tổng lượng cháo lớn nhất tìm được. Nếu không có đoạn nào có tổng chia hết cho \(K\), in ra 0.

Example

5 3
2 4 1 5 2

12

3 5
1 2 3

5