资源爆破

文件读写

• 输入文件 boom.in
• 输出文件 boom.out

限制

• 1000ms
• 512MB

题目描述

小 Y 最近在玩一个游戏 ——《爆破世界》 游戏每次会给定一个地图，大小为 (n * m)，其中每个位置都存在一个资源点，第 i 行第 j 列的资源点拥有 (a_{i,j}) 点资源 现在小 Y 有 k 个 收集炸弹，这个炸弹的效果是，选定地图上某个位置 ((i,j)) 放置（可以在同一位置重复放置炸弹），然后小 Y 可以设定这个炸弹在爆破时是 横向爆破 还是 纵向爆破

1. 横向爆破 —— 获得第 i 行所有资源点的资源值总和的收益，并使第 i 行所有资源点的资源值 (-x)
2. 纵向爆破 —— 获得第 j 列所有资源点的资源值总和的收益，并使第 j 列所有资源点的资源值 (-x) 现在小 Y 想知道，如何放置这 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)

输入格式

输入第一行包含四个整数 (n,m,k,x)，含义如题 接下来 n 行，每行 m 个整数，分别表示 (a_{i,j})

输出格式

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

国庆仿真模拟3