Maximizing Total Energy in a One‐time Weapon Battle

In this problem two combatants, A and B, each have a series of one‐time weapons. Combatant A has n weapons with energies \(a_1, a_2, \dots, a_n\) and combatant B has m weapons with energies \(b_1, b_2, \dots, b_m\). When a weapon is fired, it produces its given energy. Moreover, when A’s i-th weapon and B’s j-th weapon are used simultaneously (i.e. in the same second) an extra bonus energy \(d_{i,j}\) is released. Note that any of \(a_i\), \(b_j\) or \(d_{i,j}\) may be negative.

The battle is played over several seconds. At the moment the first weapon is fired (by at least one person) the battle begins (this is second 1). In every second, each combatant may either fire his next weapon (if available) or rest – but their weapons must be used in order. At least one combatant must fire in the first and the last second. In particular, it is not necessary that either side uses all of his weapons; the battle ends when one side has exhausted his weapons and in the following second no one fires.

However, there is an additional twist. If combatant A does not fire in two consecutive seconds – that is, if he rests for \(x\) seconds between any two successive firings – then he absorbs an energy penalty of \(Ax+B\) (where \(A,B\in\mathbb{N}\)). Similarly, if B rests for \(y\) seconds between successive firings, he absorbs \(Cy+D\) of energy (with \(C,D\in\mathbb{N}\)). Note that if a combatant fires in consecutive seconds the gap is 0 and no penalty is applied.

Your task is to decide, by choosing when to fire and when to rest (and which weapons to actually use), what is the maximum total released energy (it may be negative) by the end of the battle.

Additional explanation: You may view the battle as a scheduling problem. When a weapon is fired, its energy (and possibly a bonus if the other combatant fires simultaneously) is added to the total, but if there is any break between firings then a penalty (an affine function in the length of the break) is subtracted. Both sides choose their weapon‐firing instants subject to the order of weapons. It turns out that an optimal strategy is to fire weapons in consecutive seconds whenever possible – avoiding any unnecessary waiting time – and to use only a contiguous prefix of each sequence. In other words, if you denote by \(i_1,i_2,\dots,i_k\) the indices of weapons used by A (and similarly for B), then if \(i_{t+1}\ne i_t+1\) a penalty \(A\cdot (i_{t+1}-i_t-1)+B\) must be paid; similarly for B.

inputFormat

The input begins with a line containing six integers: n m A B C D, where n and m are the number of weapons for A and B respectively, and A, B, C, D are the penalty parameters as described above.

The next line contains n integers: a1 a2 ... an.

The following line contains m integers: b1 b2 ... bm.

Then follow n lines, each containing m integers. The j-th number in the i-th line is \(d_{i,j}\), the bonus energy released when A’s i-th weapon and B’s j-th weapon are fired simultaneously.

You may assume that all numbers are integers. You are also guaranteed that at least one of A or B fires in the first second and that the battle ends in a second when at least one of them fires.

outputFormat

Output a single integer: the maximum total energy that can be released by the end of the battle (this value might be negative).

sample

2 2 1 1 1 1
1 2
2 1
1 0
0 1

8