Cho ma trận ~A~ có ~N \times M~ phần tử. Phần tử ở hàng ~i~ cột ~j~ có giá trị là ~A_{i,j}~.

Bạn được chọn không quá ~\lfloor M/2 \rfloor~ phần tử trên mỗi hàng. Bạn hãy chọn sao cho tổng các phần tử được chọn chia hết cho ~K~ và có tổng là lớn nhất.

Dữ liệu

• Dòng đầu tiên gồm ba số nguyên ~N, M, K~ ~(1 \le N, M, K \le 70)~.

• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên biểu diễn cho ma trận ~A~. Số thứ ~j~ của dòng thứ ~i~ là ~A_{i,j}~ ~(1 \le A_{i,j} \le 70)~.

Kết quả

• Một số nguyên duy nhất thể hiện tổng các phần tử đã chọn.

Ví dụ

Sample Input

3 4 7
51 2 6 7
52 62 65 5
6 6 62 62

Sample Output

308

Giải thích

• Hàng 1 chọn 51 và 6

• Hàng 2 chọn 62 và 65

• Hàng 3 chọn 62 và 62

• Tổng các phần tử chọn là: ~51 + 6 + 62 + 65 + 62 + 62 = 308~ chia hết cho 7

Chấm điểm

• Subtask 1 (50% số test): ~1 \le N \times M \le 20~

• Subtask 2 (50% số test): Không có ràng buộc gì thêm