Background

Little A and Little B had an epic rookie battle using the brand-new equipment of the experimental base.

Problem Description

As everyone knows, weapons in the experimental base are disposable. Now, Little A picks $n$ different weapons, and Little B also gets $m$ different weapons. Each person’s weapons can be numbered from $1$ to $n$ or $m$ in order, and they will use the weapons one by one in this order.

The experimental warehouse records the firepower of all weapons. Little A’s $k$-th weapon can release $a_k$ energy, and Little B’s $k$-th weapon can release $b_k$ energy. In particular, when Little A’s $i$-th weapon and Little B’s $j$-th weapon are used at the same time, they will additionally release $d_{i,j}$ energy. Due to the special effects of some indescribable combinations, $a$, $b$, and $d$ may all be less than $0$.

When someone uses a weapon for the first time, the battle officially starts, which is counted as the $1$-st second, until after someone has finished using weapons and then nobody uses any weapon anymore; denote that moment as the $t$-th second ($t$ is not part of the input). That is, at the $1$-st second and the $t$-th second, at least one person must use a weapon, and during seconds $1$ to $t$, under the other constraints, each second both sides may choose to use the next weapon in order or not use a weapon.

To avoid killing the opponent, neither side necessarily uses all weapons.

Because the experimental base has power generators, if Little A does not continuously use weapons to release energy but rests for $x$ seconds, then they will absorb $Ax+B\ (A,B \in \mathbb{N})$ energy. Similarly, if Little B pauses for $y$ seconds, they will absorb $Cy+D\ (C,D \in \mathbb{N})$ energy. If weapons are released in two consecutive seconds, the interval is $0$ seconds, and so on.

To prevent the base from being nuked, you need to compute the maximum possible total energy that may be released after the battle ends (it may be negative).

If you are confused about the details, please read the additional explanations in the hint first.

Input Format

The first line contains two numbers $n$ and $m$.

The second line contains $n$ numbers, where the $k$-th number is $a_k$.

The third line contains $m$ numbers, where the $k$-th number is $b_k$.

Next are $n$ lines, each containing $m$ numbers. The number in row $i$ and column $j$ is $d_{i,j}$.

The last line contains four non-negative integers $A,B,C,D$.

Output Format

Only one line. Output one number, the maximum possible energy.

7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 0

45

4 4
-2 -2 -2 -2
2 3 4 9
4 -2 0 4
0 0 0 0
-1 0 1 0
0 0 2 0
1 2 1 0

15

Hint

1. The battle start time (the $1$-st second) is the time when either side first releases their first skill. The battle end time is the time when either side releases the last skill. The end time is not fixed.

2. Skills must be released in order, but they do not have to be all released during the battle.

3. $a$, $b$, and $d$ can be negative, so the total energy may be negative. “Absorbing energy” means the total energy decreases by $Ax+B$ or $Cy+D$, i.e. during an interval, the total energy always decreases, and the longer the time, the more it decreases.

4. The I/O size of this problem is large, so it is recommended to use an appropriate input method.

Sample Explanation:

Sample 1: Each person uses their weapons numbered from $1$ to $6$ in order from the $1$-st to the $6$-th second to obtain the maximum value.

Sample 2: Little B uses their weapons numbered from $1$ to $4$ in order from the $1$-st to the $4$-th second, and Little A uses their weapon $1$ at the $4$-th second to obtain the maximum value. The energy released by single weapons is $(-2)+(2+3+4+9) = 16$, the collision releases $d_{1,4} = 4$ units of energy, and Little A absorbs $A \times 3 + B = 5$ units of energy in the first $3$ seconds.

Constraints:

This problem uses bundled tests. You can get the score of a subtask only if you pass all test points in that subtask.

For $100\%$ of the testdata: $0 \le |a_k|,|b_k|,|d_{i,j}|,A,B,C,D \leq 1000$, $1\leq n, m\leq 3000$.

Translated by ChatGPT 5