Mảng dư không

Cho một ma trận $a$ kích thước $n\times m$ gồm các số nguyên.

Ở mỗi hàng, bạn được chọn không quá $\lfloor m/2\rfloor$ phần tử (số phần tử được chọn của các hàng là độc lập với nhau, và có thể chọn $0$ phần tử ở một hàng, khi đó phần đóng góp của hàng đó bằng $0$).

Hãy chọn các phần tử sao cho tổng của tất cả các phần tử được chọn chia hết cho $k$ và tổng này là lớn nhất có thể.

In ra tổng lớn nhất chia hết cho $k$ mà bạn có thể thu được. Lưu ý luôn có thể không chọn phần tử nào, khi đó tổng bằng $0$ (và $0$ chia hết cho $k$).

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên; số thứ $j$ của dòng thứ $i$ là $a_{i,j}$.

Dữ liệu ra

• Một số nguyên duy nhất: tổng lớn nhất chia hết cho $k$.

Ràng buộc

• $1\le n,m,k\le 70$
• $1\le a_{i,j}\le 70$

Ví dụ