Problem H: 28-搜索与回溯2-植物大战僵尸现实版

Problem H: 28-搜索与回溯2-植物大战僵尸现实版

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

LZH很喜欢玩植物大战僵尸的游戏,但是他的妈妈总是要让LZH学习不让LZH玩电脑游戏。于是LZH想,我能不能在现实生活中种一些植物来玩植物大战僵尸呢,这样有了绿化环境的理由妈妈就不会管我了。

于是他找了一块n*m大小的土地1*1大小的土地能种一棵植物。这块土地上已经中满了植物(没有豌豆射手),LZH在脑海中给每一种植物设定了不同的攻击力。然后LZH又打算种上最多t组(可以少于t组)豌豆射手来补充植物的攻击力,每个豌豆射手的攻击力为x。因为他是一个强迫症,所以他只会同时给一行或一列的土地种上豌豆射手,而这些地方之前种的植物就只能铲去。

通过合理种植豌豆射手能使得这片土地上植物的攻击力之和最大为多少?


Input

第一行为n, m, x, t四个整数。

1 <= n <= 10

1 <= m <= 200

1 <= x <= 10^5

0 <= t <= n + m

 接下来为一个n * m的矩阵,代表原来每1*1大小的土地上的植物的攻击力。植物攻击力y的范围:1 <= y <= 10^5


Output

输出一个整数,代表这片土地上植物最大的攻击力之和

Sample Input

3 4 1 5
10 5 7 2
10 5 10 8
3 9 5 4

Sample Output

78

[Submit][Status]