Picking Peaches

Background

Special for beginners, ^_^

Problem Description

Life has planted a field with some peach trees in it.

Life says to PFT: "I'll give you a certain amount of time to pick peaches, and you must come back to me within the given time; otherwise all the peaches you picked will be mine to eat!"

PFT thinks for a moment and finally agrees.

Because PFT is not good at math, he doesn't know how to maximize the value obtained within the given time.

Because PFT is not a robot, his stamina is not unlimited. He doesn't want to pick so many peaches that his stamina drops to $0$, only to give all the peaches to Life for nothing. Also, PFT can pick from only one peach tree at a time, and each peach tree can be picked $K$ times (the number of peaches picked each time from the same tree is the same). After each picking he must return to the starting point (PFT cannot carry much at once), which is Life's location $(0,0)$.

The coordinates of the peach at the upper-left corner of the experimental field are $(1,1)$.

PFT can move only one unit per second, and each unit of movement costs $1$ stamina (picking costs no time or stamina, and movement is restricted to up, down, left, and right).

Input Format

The first line has four numbers $N, M, TI, A$, denoting the length and width of the experimental field, the time Life gives PFT, and PFT's stamina.

This is followed by an $N$-row, $M$-column matrix of the peach field, denoting the number of peaches that can be picked from each tree each time.

This is followed by another $N$-row, $M$-column matrix, denoting the maximum number of times $K$ each tree can be picked.

Output Format

One number: the maximum number of peaches PFT can obtain.

Sample Input 1

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

Sample Output 1

10

Hint

He can pick once from $(1,1)$ and once from $(2,3)$; neither stamina nor time allows picking any more peaches.

Constraints

1s, 1024KiB for each test case.

For $M, N, TI, A$:

$30\%$ of the data is in $[10, 50]$;

$50\%$ of the data is in $[10, 100]$;

$10 \le K \le 100$.

The result is guaranteed to fit within long long.