Sửa đổi ma trận

Cho một ma trận kích thước $n\times m$. Bạn phải thực hiện đúng $k$ thao tác, mỗi thao tác thuộc một trong hai loại sau:

1. Chọn một hàng của ma trận và trừ mỗi phần tử trong hàng đó đi $p$. Thao tác này mang lại giá trị niềm vui bằng tổng các phần tử của hàng đó trước khi trừ.
2. Chọn một cột của ma trận và trừ mỗi phần tử trong cột đó đi $p$. Thao tác này mang lại giá trị niềm vui bằng tổng các phần tử của cột đó trước khi trừ.

Cùng một hàng (hoặc cùng một cột) có thể được chọn nhiều lần. Hãy tính tổng giá trị niềm vui lớn nhất có thể đạt được sau khi thực hiện đúng $k$ thao tác.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $m$, $k$, $p$.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên $a_{ij}$ là các phần tử của ma trận.

Dữ liệu ra

• In ra một số nguyên duy nhất: tổng giá trị niềm vui lớn nhất.

Ràng buộc

• $1\le n,m\le {10}^3$
• $1\le k\le {10}^6$
• $1\le p\le 100$
• $1\le a_{ij}\le {10}^3$

Ví dụ