root的果园

描述

root买了一个果园，果园里有一些果树，他对皮卡丘说，“你有一些时间去摘果子，但是你必须在时间消耗完之前回到我这里，否则你摘的果子都要归我”。

另外，皮卡丘的体力是有限的，他如果摘了太多的桃子以至体力为0，果子也会白白留给root。同时皮卡丘每次只能摘一棵果树，，每棵果树都可以摘K次（对于同一棵果树每次摘的果数相同）。每次摘完后都要返回出发点，即root的所在地（0，0）{果园左上角的果树坐标是（1，1）。

皮卡丘每秒只能移动一个单位，每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。请问皮卡丘怎样在规定的时间获得最大的果子价值呢？

数据范围：

对于M，N，TI，A 10<=30%<=50 10<=100%<=100

对于K 10<=100%<=100

保证结果在long int范围内

输入 第一行：四个数为N，M，TI，A 分别表示果园的长和宽，皮卡丘的时间和皮卡丘的体力。

下面一个N行M列的矩阵桃田。表示每次每棵果树上能摘的果数。

接下来N行M列的矩阵，表示每棵果树最多可以采摘的次数K。

输出 一个数字，皮卡丘可以获得的最大的果子的个数。

输入样例 1

4 4 13 20

17 0 0 0

0 0 17 0

0 0 10 0

0 0 0 0

1 0 0 0

0 0 2 0

0 0 4 0

0 0 0 0

输出样例 1

17

提示

样例说明：

可以摘到1次（1，1）或者 1次（2，3），然后时间和体力不满足摘果子了。