Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P165PROD - ROUND 5D - Trò chơi trên ma trận

Tại Học viện Công nghệ Bưu chính Viễn thông đang diễn ra Hội trại “Tự hào tuổi trẻ PTIT” với sự tham gia của toàn thể các clb và các chi đoàn trong trường. Và tất nhiên clb IT cũng tham gia vào sự kiên này. Để thu hút sự chú ý của mọi người, clb đã đề ra một trò chơi trên ma trận và người thắng cuộc sẽ nhận được phần thưởng rất lớn từ clb IT. Trò chơi như sau:

“ Bạn được cho một ma trận kích thước n x m và k bước chọn. Với mỗi bước chọn, bạn được chọn 1 trong 2 cách:

Cách 1: chọn 1 hàng bất kì, các ô trên hàng sẽ được cộng vào tổng S, sau đó mỗi ô trên hàng sẽ bị trừ đi một lượng là p.

Cách 2: chọn 1 cột bất kì, các ô trên cột sẽ được cộng vào tổng S, sau đó mỗi ô trên cột sẽ bị trừ đi một lượng là p.

Người chiến thắng là người đưa ra được tổng S lớn nhất.”

Lúi rất thích nhận những phần quà nhưng lại kém về các trò chơi số học hay ma trận. Các bạn hãy giúp Lúi nhận được phần thưởng từ clb IT nhé.

Input

Dòng đầu chưa 4 số nguyên n, m, k và c (0 <= n, m <= 10^3, 1 <= k <= 10^6, 1 <= p <= 100).

Trên n dòng tiếp theo mỗi dòng gồm m số a[i][j] (1 <= a[i][j] <= 10^3) là giá trị trên ô a[i][j].

Output

In ra số nguyên duy nhất là tổng S lớn nhất.

Example

Input:

2 2 3 2

1 4

2 3 Output: 13


Được gửi lên bởi:adm
Ngày:2016-03-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.