Description

Life planted a field with some peach trees.

Life said to PFT: "I will give you a certain amount of time to pick peaches. You must return to me within the time limit, otherwise all the peaches you picked will be mine to eat!"

PFT thought for a while and agreed.

Because PFT is not good at math, he does not know how to obtain the maximum total within the time limit.

PFT is not a robot, so his stamina is limited. He does not want to pick so many peaches that his stamina becomes $0$ and end up giving the peaches to Life for nothing. At the same time:

• In each trip PFT can pick from exactly one peach tree.
• Each tree can be picked at most $K$ times, and each pick from the same tree yields the same number of peaches.
• After each pick he must return to the starting point, i.e., Life's location $(0, 0)$ (the coordinate of the top-left peach in the field is $(1, 1)$).

Movement rules:

• PFT can only move up, down, left, and right.
• He moves $1$ unit per second.
• Moving $1$ unit costs $1$ stamina.
• Picking costs no time and no stamina.

Input Format

The first line contains four integers $N$, $M$, $TI$, $A$, representing the length and width of the field, the time given by Life, and PFT's stamina.

Then an $N \times M$ matrix for the field, where each entry is the number of peaches obtained per pick from that tree.

Then another $N \times M$ matrix, where each entry is the maximum number of times $K$ that tree can be picked.

Output Format

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

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

Hint

Sample explanation:

You can pick $1$ time at $(1, 1)$ and $1$ time at $(2, 3)$. Time and stamina do not allow any more picking.

Constraints:

• For $30\%$ of the testdata: $10 \le N, M, TI \le 50$.
• For $10\%$ of the testdata: $10 \le N, M, TI \le 100$.
• For $K$: $10 \le K \le 100$. The result is guaranteed to fit in the range of long int.

Translated by ChatGPT 5