OpenJudge

2919:科技庄园

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
131072kB
描述

Life种了一块田,里面种了有一些桃树。

Life对PFT说:“我给你一定的时间去摘桃,你必须在规定的时间之内回到我面前,否则你摘的桃都要归我吃!”

PFT思考了一会,终于答应了!

由于PFT的数学不好,他并不知道怎样才能在规定的时间获得最大的价值。

由于PFT不是机器人,所以他的体力并不是无限的,他不想摘很多的桃以至体力为0,而白白把桃给Life。同时PFT每次只能摘一棵桃树,每棵桃树都可以摘K次(对于同一棵桃树每次摘的桃数相同)。每次摘完后都要返回出发点(PFT一次拿不了很多),即Life的所在地(0,0){试验田左上角的桃坐标是(1,1)}。

PFT每秒只能移动一个单位,每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。

输入
输入有多组数据,每组数据第1行四个数为N,M,T1,A(10<=N,M,T1,A<=100)分别表示试验田的长和宽,Life给PFT的时间和PFT的体力。
下面一行N行M列的矩阵桃田,表示每次每棵桃树上能摘的桃数。
接下来N行M列的矩阵,表示每棵桃树最多可以采摘的次数K。
输出
输出一个数,PFT可以获得的最大的桃个数。
样例输入
4 4 13 20
10 0 0 0
0 0 10 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
样例输出
10
提示
【样例说明】
可以摘到1次(1,1)和1次(2,3),体力和时间不满足再摘桃了。

【数据范围】
M,N,TI,A数据满足:10<=30%<=50,10<=100%<=100;
K数据满足:10<=100%<=100,保证结果在long范围内。
来源
YBT
全局题号
13001
添加于
2017-01-28
提交次数
1
尝试人数
1
通过人数
1