该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在玩一个游戏——《爆破世界》

游戏每次会给定一个地图，大小为 $n * m$，其中每个位置都存在一个资源点，第 $i$ 行第 $j$ 列的资源点拥有 $a_{i,j}$ 点资源

现在徐老师有 $k$ 个 收集炸弹，这个炸弹的效果是，选定地图上某个位置 $(i,j)$ 放置（可以在同一位置重复放置炸弹），然后徐老师可以设定这个炸弹在爆破时是 横向爆破 还是 纵向爆破

1. 横向爆破——获得第 $i$ 行所有资源点的资源值总和的收益，并使第 $i$ 行所有资源点的资源值 $-x$
2. 纵向爆破——获得第 $j$ 列所有资源点的资源值总和的收益，并使第 $j$ 列所有资源点的资源值 $-x$

现在徐老师想知道，如何放置这 $k$ 个炸弹可以使得他获得最大收益（所有炸弹必须全部用完）？

P.S. 游戏为了防止过度收集，如果一个点的资源值被爆破成负数，那就是 负收益，例如某一行的资源值分别为 $[3,-5,1]$，那么横向爆破这一行时的收益就是 $3 + (-5) + 1 = -1$

输入格式

输入第一行包含四个整数 $n,m,k,x$，含义如题

接下来 $n$ 行，每行 $m$ 个整数，分别表示 $a_{i,j}$

输出格式

输出一个整数表示最大收益

数据范围

对于所有数据满足：$1 \leq n,m \leq 1000, -1000 \leq a_{i,j} \leq 1000, k \leq 1000000, 0 \leq x \leq 100$

样例输入1

2 2 2 2
1 3
2 4

样例输出1

11

样例解释1

第一次纵向爆破第 $2$ 列，收益 $3+4=7$ 地图变成

1 1
2 2

第二次横向爆破第 $2$ 行，收益 $2+2=4$

1 1
0 0

最大总收益为 $7+4=11$

样例输入2

2 2 5 2
1 3
2 4

样例输出2

11

样例解释2

在样例 $1$ 的基础上： 第三次横向爆破第 $1$ 行，收益 $1+1=2$

-1 -1
0 0

第四次横向爆破第 $2$ 行，收益 $0+0=0$

-1 -1
-2 -2

第五次横向爆破第 $1$ 行，收益 $(-1)+(-1)=-2$

-1 -1
-2 -2

最大总收益为 $7+4+2+0+(-2)=11$