P2760 Tech Manor

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.

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.

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

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